怎么全是广义后缀自动机，我(AC)自动机不服
这道题可以使用的算法很多，(SA)或者(SAM)应该都可以
但是我都不会
但是这毕竟是一个多串匹配问题，(AC)自动机还是可以刚一刚的
我们先考虑一下暴力做法
先将操作离线下来，之后对于所有的询问串建立(AC)自动机，之后我们把(n)个给出串放到(AC)自动机上跑一遍，统计一下有多少个询问串可以是其子串，给这些询问串打上标记，最后输出每一个询问串被打了几次标记就好了
但是这个做法需要我们暴力去跳(fail)指针，于是很容易被卡成平方级别
思考一下跳(fail)的实质就是在(fail)树上暴力从当前点访问到根，而最后的查询也只是查询一个子树内部不同的标记数
于是我们熟练地想到了把(fail)树抽离出来，现在的问题转化为一个子树内部有多少个不同颜色的标记
是不是非常眼熟，这不就是HH的项链多了个(dfs)序吗
于是现在莫队或者树状数组都可以上了，不过可以树状数组谁写莫队啊
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#define re register
#define maxn 360005
#define lowbit(x) ((x)&(-x))
int n,m,num,__,cnt;
struct E {int v,nxt;}e[maxn<<1];
struct Ask{int x,y,rk;}a[maxn];
char S[maxn];
std::string s[10005];
std::vector<int> v[maxn],pre[maxn];
int son[360005][26],fail[maxn],to[maxn];
int deep[maxn],dfn[maxn],head[maxn],sum[maxn],lst[maxn];
int c[maxn],f[maxn],E[100005],Ans[maxn];
inline void add_edge(int x,int y){e[++num].v=y,e[num].nxt=head[x],head[x]=num;}
inline int add(int x,int val){for(re int i=x;i<=__;i+=lowbit(i)) c[i]+=val;}
inline int ask(int x){int ans=0;for(re int i=x;i;i-=lowbit(i)) ans+=c[i];return ans;}
inline void ins(int x)
{
int now=0;
scanf("%s",S+1);
int len=strlen(S+1);
for(re int i=1;i<=len;i++)
{
if(!son[now][S[i]-'a']) son[now][S[i]-'a']=++cnt;
now=son[now][S[i]-'a'];
}
E[x]=now;
}
inline void Build()
{
std::queue<int> q;
for(re int i=0;i<26;i++) if(son[0][i]) q.push(son[0][i]);
while(!q.empty())
{
int k=q.front();
q.pop();
if(k) add_edge(fail[k],k);
for(re int i=0;i<26;i++)
if(son[k][i]) fail[son[k][i]]=son[fail[k]][i],q.push(son[k][i]);
else son[k][i]=son[fail[k]][i];
}
}
void dfs(int x)
{
dfn[++__]=x,to[x]=__;
sum[x]=1;
for(re int i=head[x];i;i=e[i].nxt)
if(!deep[e[i].v])
{
deep[e[i].v]=deep[x]+1;
dfs(e[i].v);
sum[x]+=sum[e[i].v];
}
}
inline void query(int x)
{
int len=s[x].size();
int now=0;
for(re int i=0;i<len;i++)
{
now=son[now][s[x][i]-'a'];
if(!f[now]) v[now].push_back(x);
if(!f[fail[now]])
v[fail[now]].push_back(x);
f[fail[now]]=f[now]=1;
}
now=0;
for(re int i=0;i<len;i++)
{
now=son[now][s[x][i]-'a'];
f[now]=f[fail[now]]=0;
}
}
inline int cmp(Ask A,Ask B){return A.y<B.y;}
int main()
{
scanf("%d%d",&n,&m);
for(re int i=1;i<=n;i++) std::cin>>s[i];
for(re int i=1;i<=m;i++) ins(i);
Build(),deep[0]=1,dfs(0);
for(re int i=1;i<=n;i++) query(i);
for(re int i=1;i<=m;i++) a[i].x=to[E[i]],a[i].y=to[E[i]]+sum[E[i]]-1,a[i].rk=i;
std::sort(a+1,a+m+1,cmp);
for(re int i=1;i<=__;i++)
for(re int j=0;j<v[dfn[i]].size();j++)
pre[i].push_back(lst[v[dfn[i]][j]]),lst[v[dfn[i]][j]]=i;
int top=1;
for(re int i=1;i<=__;i++)
{
for(re int j=0;j<pre[i].size();j++)
{
add(i,1);
if(pre[i][j])
add(pre[i][j],-1);
}
while(a[top].y==i)
Ans[a[top].rk]=ask(a[top].y)-ask(a[top].x-1),top++;
}
for(re int i=1;i<=m;i++) printf("%d
",Ans[i]);
return 0;
}