BZOJ2780: [Spoj]8093 Sevenk Love Oimaster（广义后缀自动机，Parent树，Dfs序）

Description

Oimaster and sevenk love each other.

But recently,sevenk heard that a girl named ChuYuXun was dating with oimaster.As a woman's nature, s

evenk felt angry and began to check oimaster's online talk with ChuYuXun. Oimaster talked with Ch

uYuXun n times, and each online talk actually is a string.Sevenk asks q questions like this, "how

many strings in oimaster's online talk contain this string as their substrings?"

有n个大串和m个询问，每次给出一个字符串s询问在多少个大串中出现过

Input

There are two integers in the first line,

the number of strings n and the number of questions q.

And n lines follow, each of them is a string describing oimaster's online talk.

And q lines follow, each of them is a question.

n<=10000, q<=60000

the total length of n strings<=100000,

the total length of q question strings<=360000

Output

For each question, output the answer in one line.

Sample Input

3 3
abcabcabc
aaa
aafe
abc
a
ca

Sample Output

1
3

解题思路：

利用Parent树的子节点都是父节点母串的性质，在大串的每个实节点打上标记，然后构建出这颗Parent树。

那么我们的问题就变成了在一个Fail节点子树内不同颜色个数。

像不像HH的项链？

把Dfs序构建出来，离线树状数组就好了。

代码：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 const int N=;

 const int M=;

 struct sant{

     int tranc[];

     int len;

     int pre;

 }s[N];

 struct pnt{

     int hd;

     int col;

     int ind;

     int oud;

 }p[N];

 struct ent{

     int twd;

     int lst;

 }e[N];

 struct qust{

     int l,r;

     int ans;

     int no;

 }q[N];

 int siz;

 int fin;

 int n,Q;

 int cnt;

 int dfn;

 char tmp[N];

 int line[N];

 int lst[N];

 int phr[N];

 int col[N];

 void Insert(int c,int whic)

 {

     int nwp,nwq,lsp,lsq;

     nwp=++siz;

     p[nwp].col=whic;

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

     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[nwp].pre=s[lsq].pre=nwq;

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

             {

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

                 lsp=s[lsp].pre;

             }

         }

     }

     fin=nwp;

     return ;

 }

 void ade(int f,int t)

 {

     cnt++;

     e[cnt].twd=t;

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

     p[f].hd=cnt;

     return ;

 }

 void Dfs(int x)

 {

     p[x].ind=++dfn;

     phr[dfn]=x;

     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;

     return ;

 }

 bool cmp(qust x,qust y)

 {

     return x.r<y.r;

 }

 bool cmq(qust x,qust y)

 {

     return x.no<y.no;

 }

 int lowbit(int x)

 {

     return x&(-x);

 }

 void update(int pos,int x)

 {

     while(pos&&pos<=siz)

     {

         line[pos]+=x;

         pos+=lowbit(pos);

     }

     return ;

 }

 int query(int pos)

 {

     int ans=;

     while(pos)

     {

         ans+=line[pos];

         pos-=lowbit(pos);

     }

     return ans;

 }

 int main()

 {

     fin=++siz;

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

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

     {

         scanf("%s",tmp+);

         fin=;

         int len=strlen(tmp+);

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

             Insert(tmp[j]-'a',i);

     }

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

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

     Dfs();

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

     {

         scanf("%s",tmp+);

         int root=;

         int len=strlen(tmp+);

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

             root=s[root].tranc[tmp[j]-'a'];

         q[i].no=i;

         if(!root)

             continue;

         q[i].l=p[root].ind;

         q[i].r=p[root].oud;

     }

     std::sort(q+,q+Q+,cmp);

     int rr=;

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

     {

         while(rr<=q[i].r)

         {

             if(!col[rr])

             {

                 rr++;

                 continue;

             }

             if(lst[col[rr]])

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

             update(rr,);

             lst[col[rr]]=rr;

             rr++;

         }

         rr--;

         if(!q[i].l)

             continue;

         q[i].ans=query(q[i].r)-query(q[i].l-);

     }

     std::sort(q+,q+Q+,cmq);

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

         printf("%d\n",q[i].ans);

     return ;

 }

巴特西