BZOJ 3238 [Ahoi2013]差异 ——后缀自动机

柔情只为你懂 2021-12-21 05:05 212阅读 0赞

后缀自动机的parent树就是反串的后缀树。

所以只需要反向构建出后缀树，就可以乱搞了。

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    #define F(i,j,k) for (int i=j;i<=k;++i)
    #define D(i,j,k) for (int i=j;i>=k;--i)
    #define ll long long
    #define maxn 1000005
     
    struct sam{
        ll ans;
        char s[maxn];
        int cnt,last,siz[maxn],len;
        int go[maxn][26],fa[maxn],l[maxn];
        int h[maxn],to[maxn],ne[maxn],en;
        void addedge(int a,int b)
        {to[en]=b;ne[en]=h[a];h[a]=en++;}
        void init()
        {
            cnt=last=1;
            memset(go,0,sizeof go);
        }
        void add(int x)
        {
    //      printf("add %d\n",x);
            int p=last,np=last=++cnt;l[np]=l[p]+1;//printf("np is %d\n",np);
            for (;p&&!go[p][x];p=fa[p]) go[p][x]=np;
            if (!p) fa[np]=1;
            else
            {
                int q=go[p][x];
                if (l[q]==l[p]+1) fa[np]=q;
                else
                {
                    int nq=++cnt; l[nq]=l[p]+1; //printf("nq is %d\n",nq);
                    memcpy(go[nq],go[q],sizeof go[q]);
                    fa[nq]=fa[q];
                    fa[np]=fa[q]=nq;
                    for (;p&&go[p][x]==q;p=fa[p]) go[p][x]=nq;
                }
            }
            siz[np]=1;
    //      printf("siz %d is %d\n",np,1);
        }
        void read()
        {
            scanf("%s",s+1); len=strlen(s+1);
            D(i,len,1) add(s[i]-'a');
        }
        void dfs(int o)
        {
    //      printf("dfs on %d len is %d\n",o,l[o]);
            for (int i=h[o];i>=0;i=ne[i])
            {
                 
                dfs(to[i]);
    //          printf("%d & %d -= %lld\n",o,to[i],(ll)2*siz[o]*siz[to[i]]*l[o]);
                ans-=(ll)2*siz[o]*siz[to[i]]*l[o];
                siz[o]+=siz[to[i]];
            }
        }
        void work()
        {
            ans=(ll)(len-1)*(len+1)*len/2;
            dfs(1);
            printf("%lld\n",ans);
        }
        void build()
        {
            en=0;
            memset(h,-1,sizeof h);
            F(i,1,cnt) addedge(fa[i],i);
        }
    }SAM;
     
    int main()
    {
        SAM.init();
        SAM.read();
        SAM.build();
        SAM.work();
    }

转载于:https://www.cnblogs.com/SfailSth/p/6486741.html