NaiveMartin's Blog

namespace sam{
    const int N=100000,L=26;
    int pr[N*2+10],ln[N*2+10],tr[N*2+10][L+10],nw;
    int make(){++nw;fill(tr[nw],tr[nw]+L,0);return nw;}
    void init(){nw=0;make();}
    int add(int c,int p){
        if(tr[p][c]){
            int q=tr[p][c];
            if(ln[q]==ln[p]+1)return q;
            else{
                int np=make();ln[np]=ln[p]+1;pr[np]=pr[q];
                copy(tr[q],tr[q]+L,tr[np]);pr[q]=np;
                for(;p&&tr[p][c]==q;p=pr[p])tr[p][c]=np;
                return np;
            }
        }else{
            int np=make();ln[np]=ln[p]+1;
            for(;p&&!tr[p][c];p=pr[p])tr[p][c]=np;
            if(!p)pr[np]=1;
            else{
                int q=tr[p][c];
                if(ln[q]==ln[p]+1)pr[np]=q;
                else{
                    int nq=make();ln[nq]=ln[p]+1;pr[nq]=pr[q];
                    copy(tr[q],tr[q]+L,tr[nq]);pr[q]=pr[np]=nq;
                    for(;p&&tr[p][c]==q;p=pr[p])tr[p][c]=nq;
                }
            }
            return np;
        }
    }
}