Manacher's Algorithm

回文串就是有一个中心，然后两边对称。就像abcba、abba。在求一个串的回文子串的时候，我们就需要枚举每一个中心，那么就有奇偶回文子串的区别了，长度是奇数的对称中心是一个字符，长度是偶数的对称中心是两个字符之间。求最长回文子串是一个典型问题，下面介绍一个O(n)的算法。

首先，对于奇偶长度的区别，这个算法的解决方法就是加入一个特殊的字符，插入每个字符之间，例如：#a#b#a#a#b#a#a#b#，这样就可以枚举到每一个中心了，就是说把两种情况都统一起来。算法的思想是利用前面已经求得的回文子串的信息，来求以当前字符中心的回文子串。设rad[i]代表以i为中心，从s[i]开始算起，回文串的半径是多少，就是单边延伸了多少个字符。现在我们要求i，有j的话，我们就先看看s[i]在不在以j为中心的回文子串（这个串设为pj）里面，其充要条件就是i越右边越好)。

一、如果不在里面的话，那么就没办法利用s[i]在pj里面的信息了，就只能穷举来求rad[i]。

二、如果在里面的话，那么在pj中，就存在s[i]的镜像s[i’] ，其中i’=j-(i-j)=2j-i ，我们就可以利用rad[i’]来求rad[i]了。那么就有三种情况:

1、在边界以内（不包括边界），那么就求得rad[i]=rad[i’]，看下图就明白为什么了

Manachers Algorithm - xxxxxxxxxxx - JWs blog

2、刚好在边界上的话，就在边界的下一个开始继续比较下去

Manachers Algorithm - xxxxxxxxxxx - JWs blog

3、如果i+ rad[i’]-1超出了pj的范围的话，那么rad[i]=j+rad[j]-i ，因为如下图，1、13不在pj里面，就是说s[1]!=s[13],而在p4里面有s[1]=s[7]，所以s[13]!=s[7]，所以不能形成更长的回文串。

Manachers Algorithm - xxxxxxxxxxx - JWs blog

还有个优化就是，我们当前求得的最长半径是r的话，那么我们知道当i超过一定的位置时，半径最大也不会超过r，这个位置就是k=i+len-(r+i)=len-r。整段程序代码如下：

int lps(char *s,int *rad)
{
     int len = (strlen(s)<<1)+2,i=2,r=1;
    int k=len-1,max=0,cen=0;//max代表最远覆盖到哪里
    char str[MAXD]={‘$’,’#’};//第一个放$是为了防止越界
    while(i<len)  {str[i++]=*s++; str[i++] = '#';}
    s = str;
    rad[0]=rad[1]=1;
    for(i=2; i<k; ++i) {
                 if(max > i)
                       rad[i] = rad[(cen<<1)-i]<max-i ? rad[(cen<<1)-i] : max-i;
                else
                       rad[i] = 1;
                while(s[i+rad[i]] == s[i-rad[i]]) ++rad[i];
                if(rad[i]>r) {r=rad[i];k=len-r+1;}
                if(rad[i]+i-1 > max) {
                             max = i+rad[i]-1;
                             cen = i;
                }
    }
    return r-1;
}

因为每个字符都跟一个#配套，所以半径就乘以2了，然后会多出一个#没和字符配套，所以要-1，所以放回r-1就是最长的长度了.

附oj地址：http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=19933