A Problem on FFT and Strings

Revision en1, by -synx-, 2017-03-08 17:00:14

We are given 2 lines (DNA Sequences) of equal length of upto 105 characters consisting of alphabets A, T, G, C only.
We have to find the ith cyclic shift of one string for which maximum characters are matched between the two strings.
We have to do it in better than O(n2) obviously. Any hints?

Tags fft, #strings

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English -synx- 2017-03-08 17:00:14 338 Initial revision (published)