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


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