【BZOJ3756】Pty的字符串（广义后缀自动机）

题意：

思路：论文题

建立Trie树的后缀自动机需要换这个长的板子

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef pair<ll,ll> Pll;

 typedef vector<int> VI;

 typedef vector<PII> VII;

 typedef pair<ll,int>P;

 #define N  800010

 #define M  8100000

 #define fi first

 #define se second

 #define MP make_pair

 #define pi acos(-1)

 #define mem(a,b) memset(a,b,sizeof(a))

 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)

 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)

 #define lowbit(x) x&(-x)

 #define Rand (rand()*(1<<16)+rand())

 #define id(x) ((x)<=B?(x):m-n/(x)+1)

 #define ls p<<1

 #define rs p<<1|1

 const int MOD=1e9+,inv2=(MOD+)/;

       double eps=1e-;

       int INF=1e9;

       ll inf=5e13;

       int dx[]={-,,,};

       int dy[]={,,-,};

 char s[M];

 int p,np,q,nq,k,cas,n;

 int pos[N];

 int read()

 {

    int v=,f=;

    char c=getchar();

    while(c<||<c) {if(c=='-') f=-; c=getchar();}

    while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();

    return v*f;

 }

 struct sam

 {

     int cnt;

     int fa[N<<],ch[N<<][];

     int st[N<<],b[N<<],bl[N<<],to[N<<],size[N<<];

     ll f[N<<];

     sam()

     {

         cnt=;

     }

     int add(int p,int x)

     {

         if(ch[p][x])

         {

             q=ch[p][x];

             if(st[q]==st[p]+)

             {

                 size[q]++;

                 return q;

             }

              else

              {

                  st[nq=++cnt]=st[p]+; size[nq]=;

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

                 //t[nq]=t[q];

                  fa[nq]=fa[q];

                  fa[q]=nq;

                  while(ch[p][x]==q)

                  {

                      ch[p][x]=nq;

                      p=fa[p];

                  }

                  return nq;

              }

         }

          else

          {

                 st[np=++cnt]=st[p]+; size[np]=;

                 while(p&&!ch[p][x])

                 {

                     ch[p][x]=np;

                     p=fa[p];

                 }

                 if(!p) fa[np]=;

                  else

                  {

                         int q=ch[p][x];

                         if(st[q]==st[p]+) fa[np]=q;

                          else

                          {

                                 nq=++cnt; st[nq]=st[p]+;

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

                                 fa[nq]=fa[q];

                                 fa[q]=fa[np]=nq;

                                 while(ch[p][x]==q)

                                 {

                                     ch[p][x]=nq;

                                     p=fa[p];

                                 }

                          }

                  }

            }

         return np;

     }

     void solve()

     {

         //printf("cnt=%d\n",cnt);

         rep(i,,cnt) b[st[i]]++;

         rep(i,,cnt) b[i]+=b[i-];

         rep(i,,cnt) bl[b[st[i]]--]=i;

         scanf("%s",s+);

         int n=strlen(s+);

         per(i,cnt,) size[fa[bl[i]]]+=size[bl[i]];

         //rep(i,1,cnt) printf("%d\n",size[i]);

         size[]=;

         rep(i,,cnt)

         {

             int p=bl[i];

             f[p]=f[fa[p]]+1ll*(st[p]-st[fa[p]])*size[p];

         }

         ll ans=;

         p=;

         int L=;

         rep(i,,n)

         {

             int x=s[i]-'a';

             if(ch[p][x]) L++,p=ch[p][x];

              else

              {

                  while(p&&!ch[p][x]) p=fa[p];

                  if(p) L=st[p]+,p=ch[p][x];

                   else L=,p=;

              }

              if(p!=) ans+=f[fa[p]]+1ll*(L-st[fa[p]])*size[p];

         }

         printf("%lld\n",ans);

     }

 }sam;

 int main()

 {

     freopen("1.in","r",stdin);

     freopen("1.out","w",stdout);

     n=read();

     pos[]=;

     rep(i,,n)

     {

         int x=read();

         scanf("%s",s+);

         pos[i]=sam.add(pos[x],s[]-'a');

     }

     sam.solve();

     return ;

 }