【模板】后缀自动机

struct SuffixAutoMaton{
    int pool=1,len[N],nxt[N][27],last=1,fail[N];
    void init(){
        for(int i=1;i<=pool;++i)memset(nxt[i],0,sizeof(nxt[i]));
        last=pool=1;
    }
    void extend(char *s,int x){
        int c=s[x]-'a',p=last,cur=++pool;
        len[cur]=len[p]+1;
        for(;p&&!nxt[p][c];p=fail[p])nxt[p][c]=cur;
        if(!p)fail[cur]=1;
        else{
            int q=nxt[p][c];
            if(len[p]+1==len[q])fail[cur]=q;
            else{
                int clone=++pool;
                len[clone]=len[p]+1;
                fail[clone]=fail[q];
                memcpy(nxt[clone],nxt[q],sizeof(nxt[q]));
                for(;p&&nxt[p][c]==q;p=fail[p])nxt[p][c]=clone;
                fail[q]=fail[cur]=clone;
            }
        }
        last=cur;
    }
}sam;