Manacher算法是一个O(n)复杂度的寻找最大回文串的算法。
Manacher利用对称的思想，将奇对称和偶对称结合起来，已知字符串前mx个字符中的最大回文串的中心为id，从中心到边界的长度为mx-id以及以前id个字符为中心的最大回文串长度集合p[n]。则以第i个字符为中心的最大回文串的长度的下界为
min(p[2*id-i],mx-i)
然后以此为下界扩充回文串的长度。
为了把所有的回文串归纳为次情况，它还对原始串进行处理，将每一个字符用特殊字符隔开(如'#');
例题：

Palindrome

POJ - 3974

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int MAX_N=2000020;
char s[MAX_N],ss[MAX_N];
int p[MAX_N];
int t;
int manecher(const char* str){
    int mx=0;
    int id=0;
    int ans=0,aid=0;
    int n=strlen(str);
    for(int i=0;i<n;i++){
        if(i<mx){
            p[i]=min(p[2*id-i],mx-i);
        }
        else
            p[i]=1;
        while(str[i+p[i]]==str[i-p[i]])
            p[i]++;
        if(i+p[i]>mx){
            mx=p[i]+i;
            id=i;
        }
        if(p[i]-1>ans)
        {
           ans=p[i]-1;
           aid=i;
        }
    }
    return ans;
}
int main(){
    int c=0;
    while(~scanf("%s",s)){
        if(strcmp(s,"END")==0){
            return 0;
        }
        int n=strlen(s);
        int j=0;
        ss[j++]='$';
        for(int i=0;i<n;i++){
            ss[j++]='#';
            ss[j++]=s[i];
        }
        ss[j++]='#';
        ss[j]='\0';
        printf("Case %d: %d\n",++c,manecher(ss));
    }
    return 0;
}

Making Huge Palindromes

LightOJ - 1258

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX_N=1000003;
int n,m,t;
int len;
char s1[MAX_N],s2[MAX_N*2];
int p[MAX_N*2];
int manecher(const char* str)
{
    int id=0,mx=0;
    int ans=0;
    int ll=strlen(str);
    for(int i=0;i<ll;i++){
        if(i<mx){
            p[i]=min(p[2*id-i],mx-i);
        }else{
            p[i]=1;
        }
        while(str[i+p[i]]==str[i-p[i]])
            p[i]++;
        if(p[i]+i>mx){
            mx=p[i]+i;
            id=i;
        }
        if(mx==ll){
            ans=p[i]-1;
            break;
        }
    }
    return ans;
}
int main(void){
    scanf("%d",&t);
    int c=0;
    while(t--){
        scanf("%s",s1);
        len=strlen(s1);
        int j=0;
        s2[j++]='$';
        for(int i=0;i<len;i++){
            s2[j++]='#';
            s2[j++]=s1[i];
        }
        s2[j++]='#';
        s2[j]='\0';
        printf("Case %d: %d\n",++c,2*len-manecher(s2));
    }
}

吉哥系列故事——完美队形II

HDU - 4513

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX_N=1000003;
int n,m,t;
int len;
int s1[MAX_N],s2[MAX_N*2];
int p[MAX_N*2];
int manecher(const int* str)
{
    int id=0,mx=0;
    int ans=0;
    for(int i=0;i<len*2+1;i++){
        if(i<mx){
            p[i]=min(p[2*id-i],mx-i);
        }else{
            p[i]=1;
        }
        if(str[i+p[i]]==str[i-p[i]]){
           p[i]++;
           while(str[i+p[i]]==str[i-p[i]]&&(str[i+p[i]]<0||str[i+p[i]]<=str[i+p[i]-2]))
                p[i]++;
        }
        if(p[i]+i>mx){
            mx=p[i]+i;
            id=i;
        }
        ans=max(ans,p[i]-1);
    }
    return ans;
}
int main(void){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&len);
        int j=0;
        s2[j++]=-2;
        for(int i=0;i<len;i++){
            s2[j++]=-1;
            scanf("%d",&s2[j++]);
        }
        s2[j++]=-1;
        s2[j]=-1;
        printf("%d\n",manecher(s2));
    }
}