【算法】回文树

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn=100010;struct trees{
    int len,fail,t[260];}t[maxn];char s[maxn];int n,len,l,sz,ans;int getfail(int x){    while(s[len-t[x].len-1]!=s[len])x=t[x].fail;    return x;}void tree_work(){    int x=s[++len];    l=getfail(l);    if(!t[l].t[x])    {        sz++;        t[sz].len=t[l].len+2;        if(t[sz].len>ans)ans=t[sz].len;        t[sz].fail=t[getfail(t[l].fail)].t[x];//偏小         t[l].t[x]=sz;    }    l=t[l].t[x];}int main(){    scanf("%s",s+1);    n=strlen(s+1);    sz=1;    s[0]=-1;//    t[0].len=0;t[1].len=-1;    t[0].fail=t[1].fail=1;    len=l=ans=0;    for(int i=1;i<=n;i++)tree_work();    printf("%d",ans);    return 0;}