回文ツリー学習ノート(テンプレート)

 
回文樹をよく理解しました.
理解した后の感じ:どうして前にとても复雑だと感じますか?Orz
 
自分の理解に基づいて自分が読めるテンプレートを変更しました.
 

#include
using namespace std;
const int maxn=1e5+50;

int last,tot,n;
int next[maxn][27],len[maxn],fail[maxn],s[maxn],cnt[maxn]; 
/*
n         
last                      1  
next[i][j]   i        x                
len[i]  i            
fail[i]    i             
s[i]       i    
cnt[i]  i                       
*/
inline void init()
{
    s[0]=-1;fail[0]=1;last=0;
    len[0]=0;len[1]=-1;tot=1;
}
/*
              1     1        len[1]=1;
       ：
         (  2)             :-1+2=1
*/
inline int getfail(int x,int id)
{
    while(s[id-len[x]-1]!=s[id])x=fail[x];
    return x;
}
/*
 x                               
             
    ，      1                      1    
len[1]=-1   
                1     :
(s[id-len[1]-1]=s[id-(-1)-1])==s[id] 
*/ 
inline int newnode(int x)
{
    len[++tot]=x;
    return tot;
}
inline int solve()
{
    int i,p,q;
    init();
    for(i=1;i<=n;i++)
    {
        p=getfail(last,i);
        //          s[i]               p 
        if(next[p][s[i]]==0)//   p         s[i]    
        {
            printf("%d %d ",i,q);
            q=newnode(len[p]+2);//     p     s[i]
            fail[q]=next[getfail(fail[p],i)][s[i]];
            //q         p         s[i]         s[i]               0
            next[p][s[i]]=q;
            
            for(int j=i-len[q]+1;j<=i;j++)printf("%c",s[j]+'a');
            putchar(10);
        }
        last=next[p][s[i]];//            
        cnt[next[p][s[i]]]++;//          +1 
    }
    for(i=tot;i>1;i--)
    {
        cnt[fail[i]]+=cnt[i];
        /*
        i                
                          
                                      
        */ 
    }
}
int main()
{
    char s1[maxn];
    scanf("%s",s1);
    n=strlen(s1);
    for(int i=1;i<=n;i++)s[i]=s1[i-1]-'a';
    solve();
}

 
2019-09-10 22:39:54