HiHo 1032 最长回文子串 (Manacher算法求解)

/**
*   求解最长回文字串，Manacher算法o(n)求解最长回文子串问题
**/

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
#define L 2000050
using namespace std;
char line[L],str[L];
int cnt[L],len1,len2;

int main(){
    int ans,t,i,j;
    scanf("%d",&t);
    while(t--){
        scanf("%s",line);
        len1=strlen(line);
        len2=0;
        str[len2++]='$';
        str[len2++]='#';
        for(i=0;i<len1;i++){
            str[len2++]=line[i];
            str[len2++]='#';
        }
        str[len2]='';
        memset(cnt,0,sizeof cnt);
        for(i=1,j=0;i<len2;i++){
            if(cnt[j]+j>i)cnt[i]=min(cnt[2*j-i],cnt[j]-(i-j));
            else cnt[i]=1;
            for(;str[i-cnt[i]] == str[i+cnt[i]];cnt[i]++);
            if(i+cnt[i]>j+cnt[j])j=i;
        }
        //puts(str);
        ans=0;
        for(i=0;i<len2;i++)
        {
           // printf("%d ",cnt[i]);
            if(ans<cnt[i])ans=cnt[i];
        }
        printf("%d
",ans-1);
    }
    return 0;
}