[备忘] Manacher算法

原文链接：http://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-palindrome-sub-string/

A simple linear time algorithm for finding longest palindrome sub-string

August 2, 2009 by stone

Given a string 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, then we have 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 So the number of overall comparisons is a most 2N.

引入‘#’去除奇、偶分别；

记录之前比较回文串扩展到右端的最大下标 P[a]+a = max{ P[j]+j :  j<i }

则 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])} 可去除多余比较，直接进行有用的扩展； 贴代码备忘：

void manacher()
{
    int i;
    int mx = 0;
    int id;
    for (i=1; i<n; i++)
    {
        if ( mx > i )
            p[i] = min( p[2*id-i], mx-i );
        else
            p[i] = 1;
        for (; str[i+p[i]] == str[i-p[i]]; p[i]++)
            ;
        if ( p[i] + i > mx )
        {
            mx = p[i] + i;
            id = i;
        }
    }
}