*S*, we are to find the longest sub-string

*s*of

*S*such that the reverse of

*s*is exactly the same as

*s*.

First insert a special character ‘#’ between each pair of adjacent characters of

*S*, in front of

*S*and at the back of

*S*. After that, we only need to check palindrome sub-strings of odd length.

Let

*P[i]*be the largest integer

*d*such that S[i-d,…,i+d] is a palindrome. We calculate all

*P[i]*s from left to right. When calculating

*P[i]*, we have to compare S[i+1] with S[i-1], S[i+2] with S[i-2] and so on. A comparison is successful if two characters are the same, otherwise it is unsuccessful. In fact, we can possibly skip some unnecessary comparisons utilizing the previously calculated

*P[i]*s.

Assume

*P[a]+a=max{ P[j]+j : j<i }.*If

*P[a]+a >= i*, then we have

*.*

P[i] >= min{ P[2*a-i], 2*a-i-(a- P[a])}

P[i] >= min{ P[2*a-i], 2*a-i-(a- P[a])}

Is it the algorithm linear time? The answer is yes.

First the overall number of unsuccessful comparisons is obviously at most

*N*.

A more careful analysis show that

*S[i]*would never be compared successfully with any

*S[j](j<i)*after its first time successful comparison with some

*S[k] (k<i)*.

So the number of overall comparisons is a most

*2N*.

It turns out that this algorithm is called Manacher’s algorithm.