JDOJ 2939: Suffix Automaton 广义后缀自动机_统计子串

建立广义后缀自动机，对每个节点都建立各自的 $Parent$ 数组.

这样方便统计，不会出现统计错误.

考虑新加入一个字符.

1 这条转移边已经存在，显然对答案没有贡献.

2 这条转移边不存在，贡献即为 $dis[np]-dis[f[np][id]]$

考虑一下为什么 2 是对的.

当新建一个节点时，新加入的子串在后缀自动机上体现为边跳边新连的那些转移边，由于这些

点都是祖父关系，故直接剪掉最上方的父亲的最大长度即可.

Code:

#include <cstdio>

#include <algorithm>

#include <cstring>

#define setIO(s) freopen(s".in","r",stdin)

#define maxn 600000

#define N 30

#define ll long long

using namespace std;

char str[maxn];

int last=1,tot=1,n,m;

int ch[maxn][N],cnt[maxn][2],f[maxn][7],dis[maxn],rk[maxn];

long long C[maxn],ans;

void ins(int c,int id){

    int np=++tot,p=last; last=np;

    if(ch[p][c]){

        int q=ch[p][c];

        if(dis[q]==dis[p]+1) last=q;

        else {

            int nq=++tot; last=nq;

            f[nq][id]=f[q][id],dis[nq]=dis[p]+1;

            memcpy(ch[nq],ch[q],sizeof(ch[q]));

            f[q][id]=nq;

            while(p&&ch[p][c]==q) ch[p][c]=nq,p=f[p][id];

        }

    }

    else{

        dis[np]=dis[p]+1;

        while(p&&!ch[p][c]) {  ch[p][c]=np,p=f[p][id]; }

        if(!p) f[np][id]=1;

        else{

            int q=ch[p][c],nq;

            if(dis[q]==dis[p]+1) f[np][id]=q;

            else{

                nq=++tot;

                dis[nq]=dis[p]+1;

                memcpy(ch[nq],ch[q],sizeof(ch[q]));

                f[nq][id]=f[q][id],f[q][id]=f[np][id]=nq;

                while(p&&ch[p][c]==q) ch[p][c]=nq,p=f[p][id];

            }

        }

        ans+=(dis[np]-dis[f[np][id]]);

    }

}

int main(){

    //setIO("input");

    int t; scanf("%d",&t);

    while(t--)

    {

        scanf("%s",str),n=strlen(str);

        for(int i=0;i<n;++i) ins(str[i]-'a',0),printf("%lld\n",ans);

        last = 1;

    }

    return 0;

}