We are given 2 lines (DNA Sequences) of equal length of upto 10^{5} characters consisting of alphabets *A*, *T*, *G*, *C* only.

We have to find the *i*^{th} cyclic shift of one string for which maximum characters are matched between the two strings.

We have to do it in better than *O*(*n*^{2}) obviously. Any hints?

Suppose that strings are composed only by 0 and 1.. If the text is

swithlength(s) =nand the pattern istwithlength(t) =m, reverse the pattern first, and then for each string build the polynomialP(w) =w[0] +w[1] ×x+ ... +w[length(w) - 1] ×x^{length(w) - 1}. The coefficient of the termi+m- 1 inP(s+s) ×P(rev(t)) give you the matches of thei- th cyclic shift ofswitht.. For solving the original problem calculate the answer for each different letters and add up the result for obtain the answer for the original.x^{5}+x^{4}+ 1.poly(S_{1}) andpoly(reversed(S_{2})) modulox^{n}- 1. Modulo means setting the relationx^{n}= 1 which is saying that rotating left bynchanges nothing. To implement: the result of multiplication has size 2n, just add the high half to the low and remove the high half). Reverse is needed because normal convolution will pair first letters "asymmetrically".