回文树学习笔记-白红宇

回文树学习笔记

阅读量：6972 次

发布时间：2019-06-27

本文共 1103 字，大约阅读时间需要 3 分钟。

作为一枚懒人我怎么可能自己写那咕咕咕

这个挺好哒

然后回文树实际是可以可持久化哒(什么不能啊/xyx)

我们可以把get_fail那一部分用数组存下来，然后可持久化这个数组即可

就先不仔细研究这个玩意了吧咕咕咕

模板()

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;int n,fail[300100],son[300100][30],ans[300100],len[300100],cnt,last;long long Ans;char s[300100];inline void new_node(int x){len[++cnt]=x;ans[cnt]=0;}inline int get_fail(int x,int n){ while(s[n]!=s[n-len[x]-1])x=fail[x]; return x;}inline void build(){ for(int i=1;i<=n;i++){ int x=s[i]-'a',now=get_fail(last,i); if(!son[now][x]){ new_node(len[now]+2); fail[cnt]=son[get_fail(fail[now],i)][x]; son[now][x]=cnt; } last=son[now][x]; ans[last]++; }}int main(){ scanf("%s",s+1); n=strlen(s+1); cnt--; new_node(0),new_node(-1); fail[1]=fail[0]=1; last=0; build(); for(int i=cnt;i>=0;i--)ans[fail[i]]+=ans[i]; for(int i=0;i<=cnt;i++)Ans=max(Ans,(long long)len[i]*ans[i]); cout<