Manacher算法模板

http://poj.org/problem?id=3974

//O(N)计算一个给定字符串的最长回文子串
const int MM = 1111111; 
char str[MM],ch[MM<<2];
int rad[MM<<2], N;

void get_init() {
    int i,j,k;ch[0]='$', ch[1]='#';
    for(i=0;str[i];i++) ch[(i<<1)+2]=str[i],ch[(i<<1)+3]='#';
    N=(i<<1)+2, ch[N]='\0';
}
int Manacher() {
    int i,j,k,mx=0,id; get_init();    
    for(i=1;i<N;i++) {
         if(mx>i) rad[i]=f_min(rad[(id<<1)-i],mx-i);
         else rad[i]=1;
         for(;ch[i-rad[i]]==ch[i+rad[i]];rad[i]++);
         if(rad[i]+i>mx)  mx=rad[i]+i,id=i;
    }
    int ans=-1;
    for(i=1;i<N;i++) if(ans==-1||ans<(rad[i]-1)) ans=rad[i]-1;
    return ans;
} 

void solve() {
    printcase();
    printf("%d\n",Manacher());
}

int main() {
    while(scanf("%s",str),str[0]!='E') solve();
    return 0;
}