[文章目录]
Description
给你n个串，和q组询问，每次询问一个字符串是多少个串的子串。n<=10^4，串长和<=10^5，q<=6*10^4，串长和<=36*10^4
广义后缀自动机，将每个串的后缀树的每个节点+1。查询的时候直接到后缀自动机中拿出答案即可。据说时间复杂度极限是O(n√n) 的？？？
想要nlogn的话可以把后缀树拿出来做树链的并了，不过我懒。。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
int n,m,l[11000],r[11000];
int last=1,tot=1,ch[N<<1][26],pre[N<<1],dep[N<<1],siz[N<<1],vis[N<<1];
char st[N<<2];
void insert(int x)
{
int p=last;
if(ch[p][x])
{
int q=ch[p][x];
if(dep[q]==dep[p]+1) last=q;
else
{
int clo=++tot; last=clo;
memcpy(ch[clo],ch[q],sizeof(ch[q]));
pre[clo]=pre[q],dep[clo]=dep[p]+1,pre[q]=clo;
for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=clo;
}
}
else
{
int cur=++tot;
last=cur; dep[cur]=dep[p]+1;
for(;p&&!ch[p][x];p=pre[p]) ch[p][x]=cur;
if(!p) pre[cur]=1;
else
{
int q=ch[p][x];
if(dep[q]==dep[p]+1) pre[cur]=q;
else
{
int clo=++tot;
memcpy(ch[clo],ch[q],sizeof(ch[q]));
dep[clo]=dep[p]+1,pre[clo]=pre[q],pre[q]=pre[cur]=clo;
for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=clo;
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
int i,j,p,k,len;
for(i=1;i<=n;++i)
{
l[i]=r[i-1]+1;
scanf("%s",st+l[i]);
r[i]=strlen(st+1); last=1;
for(j=l[i];j<=r[i];++j) insert(st[j]-'a');
}
for(i=1;i<=n;++i)
for(p=1,j=l[i];j<=r[i];++j)
{
p=ch[p][st[j]-'a'];
for(k=p;k&&vis[k]!=i;k=pre[k]) vis[k]=i,siz[k]++;
}
while(m--)
{
scanf("%s",st+1);
len=strlen(st+1); j=1;
for(i=1;i<=len;++i) j=ch[j][st[i]-'a'];
if(i!=len+1) puts("0");
else printf("%d\n",siz[j]);
}
return 0;
}