后缀自动机

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
namespace SAM
{
    static const int Sigma=26;
    signed fa[MAX],ch[MAX][Sigma],len[MAX];
    int last=1,tot=1;
    inline int get(char c) {return c-'a';}
    inline void copy(int P,int Q) {for(int i=0;i<Sigma;++i) ch[P][i]=ch[Q][i]; fa[P]=fa[Q],len[P]=len[Q];}
    inline void Extend(int c)
    {
        int p=last,newp=last=++tot; f[tot]=1;
        len[newp]=len[p]+1;
        for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=newp;
        if(!p) return fa[newp]=1,void();
        int q=ch[p][c];
        if(len[q]==len[p]+1) return fa[newp]=q,void();
        int newq=++tot; copy(newq,q);
        len[newq]=len[p]+1,fa[q]=fa[newp]=newq;
        for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=newq;
    }
}