A Problem on FFT and Strings

Правка en1, от -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?

Теги fft, #strings

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский -synx- 2017-03-08 17:00:14 338 Initial revision (published)