Question

Devise an algorithm to generate the set of strings with the exact Hamming distance of d from a given string P. What is the running time of the algorithm in term of Big-O notation? (Looking for Psuedo-code, empthasis on the Big-O notation)

Answer 1

Algorithm:

1.get the input string and input the exact hamming distance

2.Get all substrings and store in an string array

3.run 2 loops to take two strings all a time to calculate length

4.If length is same,check number of diffferent characters in string at same positions that is hamming distance

5.Check if hamming distance calculated is equal to inputted hamming distance

6.If yes then print both sub strings

Pseudo Code-

given_string=input(string)

given_hamming_distance=input(exact hamming distance)

substrings=get_all_substring(given_string)

for i=1 to length(substring)

{

for j=i+1 to length(substring)

{

if(length(substring[i])==length(substring[j]))

{ count=0

for k1=1 to length(substring[i]) , k2=1 to length(substring[j])

{

if(substring[i][k1]==substring[j][k2])

count++;

}

if(count==exact_hamming_distance)

{

print substring[i],substring[j]

}

}

}

}

the complexity of above is O(n^3)