BZOJ3277: 串（后缀自动机，Parent树，Dfs序）

Description

字符串是oi界常考的问题。现在给定你n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中

至少k个字符串的子串（注意包括本身）。

Input

第一行两个整数n，k。

接下来n行每行一个字符串。

n,k,l<=100000

Output

输出一行n个整数，第i个整数表示第i个字符串的答案。

Sample Input

3 1
abc
a
ab

Sample Output

6 1 3

解题思路：

k个嘛，好像可以离线树状数组QAQ，具体的像这样，只不过需要将所有节点都询问一遍。

最后，找子串嘛，短的不多于k个长的肯定也不行，利用这个性质，只要不够k就跳pre，直到大于等于k。

而以这个节点为后缀的子串共有len个，ans+=len就好了。

代码：

 #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++)

     {

         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+=s[root].len;

         }

         printf("%d ",ans);

     }

     puts("");

     return ;

 }