codeforces 204E. Little Elephant and Strings(广义后缀自动机，Parent树)

传送门在这里。

大意：

　　给一堆字符串，询问每个字符串有多少子串在所有字符串中出现K次以上。

解题思路：

　　这种子串问题一定要见后缀自动机Parent树Dfs序统计出现次数都是套路了吧。

这道题统计子串个数，那么可以发现，若一个节点所对应的子串出现了K次，那么其贡献就是len，不需要考虑重复。

因为即使出现重复也是在两个位置。

那么只需统计以每个点结束的子串就好了。

之前的Dfs序就很套路了。

只需再跑一遍字符串，更新答案就好了。

代码：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 const int N=;

 struct sant{

     int tranc[];

     int len;

     int pre;

 }s[N];

 struct pnt{

     int hd;

     int ind;

     int oud;

     int col;

     int ans;

 }p[N];

 struct ent{

     int twd;

     int lst;

 }e[N];

 struct int_2{

     int l;

     int r;

     int no;

 }d[N];

 int n,k;

 int siz;

 int dfn;

 int cnt;

 int fin;

 char tmp[N];

 int ll[N],rr[N];

 int col[N];

 int lst[N];

 int line[N];

 int str[N];

 int lowbit(int x)

 {

     return x&(-x);

 }

 void update(int pos,int x)

 {

     while(pos&&pos<=dfn)

     {

         line[pos]+=x;

         pos+=lowbit(pos);

     }

     return ;

 }

 int query(int pos)

 {

     int ans=;

     while(pos)

     {

         ans+=line[pos];

         pos-=lowbit(pos);

     }

     return ans;

 }

 bool cmp(int_2 x,int_2 y)

 {

     return x.r<y.r;

 }

 void ade(int f,int t)

 {

     cnt++;

     e[cnt].twd=t;

     e[cnt].lst=p[f].hd;

     p[f].hd=cnt;

     return ;

 }

 void Insert(int c,int pl)

 {

     int nwp,nwq,lsp,lsq;

     nwp=++siz;

     s[nwp].len=s[fin].len+;

     p[nwp].col=pl;

     for(lsp=fin;lsp&&!s[lsp].tranc[c];lsp=s[lsp].pre)

         s[lsp].tranc[c]=nwp;

     if(!lsp)

         s[nwp].pre=;

     else{

         lsq=s[lsp].tranc[c];

         if(s[lsq].len==s[lsp].len+)

             s[nwp].pre=lsq;

         else{

             nwq=++siz;

             s[nwq]=s[lsq];

             s[nwq].len=s[lsp].len+;

             s[lsq].pre=s[nwp].pre=nwq;

             while(s[lsp].tranc[c]==lsq)

             {

                 s[lsp].tranc[c]=nwq;

                 lsp=s[lsp].pre;

             }

         }

     }

     fin=nwp;

 }

 void Dfs(int x)

 {

     p[x].ind=++dfn;

     col[dfn]=p[x].col;

     for(int i=p[x].hd;i;i=e[i].lst)

     {

         int to=e[i].twd;

         Dfs(to);

     }

     p[x].oud=++dfn;

     col[dfn]=p[x].col;

 }

 int main()

 {

     scanf("%d%d",&n,&k);

     if(k>n)

     {

         for(int i=;i<=n;i++)

             printf("%d ",);

         return ;

     }

     fin=++siz;

     for(int i=;i<=n;i++)

     {

         ll[i]=rr[i-]+;

         rr[i]=rr[i-];

         fin=;

         scanf("%s",tmp);

         int len=strlen(tmp);

         for(int j=;j<len;j++)

             str[++rr[i]]=tmp[j]-'a';

         for(int j=ll[i];j<=rr[i];j++)

         {

             Insert(str[j],i);

         }

     }

     for(int i=;i<=siz;i++)

         ade(s[i].pre,i);

     Dfs();

     for(int i=;i<=siz;i++)

         d[i]=(int_2){p[i].ind,p[i].oud,i};

     std::sort(d+,d+siz+,cmp);

     int r=;

     for(int i=;i<=siz;i++)

     {

         while(r<=d[i].r)

         {

             if(!col[r])

             {

                 r++;

                 continue;

             }

             if(lst[col[r]])

                 update(lst[col[r]],-);

             update(r,);

             lst[col[r]]=r;

             r++;

         }

         r--;

         p[d[i].no].ans=query(d[i].r)-query(d[i].l-);

     }

     for(int i=;i<=n;i++)

     {

         long long int ans=;

         int root=;

         for(int j=ll[i];j<=rr[i];j++)

         {

             root=s[root].tranc[str[j]];

             while(p[root].ans<k)

                 root=s[root].pre;

             ans+=(long long)s[root].len;

         }

         printf("%I64d ",ans);

     }

     puts("");

     return ;

 }