题解：
对于所有n串建广义后缀自动机。
（广义后缀自动机唯一区别就是每次将las附成1，并不需要在插入时特判）
建完后再建出parent树，然后用dfs序+树状数组搞区间不同种类。
其实就是HH的项链+广义后缀自动机。很水的。（虽然我调了半个晚上）
代码：
#include<vector> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 100050 int n,q; char s[360050]; int ic(char c) { if(c>='a'&&c<='z')return c-'a'+1; if(c>='A'&&c<='Z')return c-'A'+27; if(c>='0'&&c<='9')return c-'0'+53; if(c==',')return 63; if(c=='.')return 64; return 65; } int tin[2*N],tout[2*N],tim,pla[2*N]; struct SAM { struct node { int len,pre,trs[68]; vector<int>v; }p[2*N]; int tot,las; SAM(){tot=las=1;} void res(){las=1;} void insert(int c,int k) { int np,nq,lp,lq; np = ++tot; p[np].len = p[las].len+1; for(lp=las;lp&&!p[lp].trs[c];lp=p[lp].pre) p[lp].trs[c]=np; if(!lp)p[np].pre = 1; else { lq = p[lp].trs[c]; if(p[lq].len == p[lp].len+1)p[np].pre = lq; else { nq = ++tot; p[nq] = p[lq]; p[nq].len = p[lp].len+1; p[lq].pre = p[np].pre = nq; while(p[lp].trs[c]==lq) { p[lp].trs[c]=nq; lp=p[lp].pre; } } } las = np; p[las].v.push_back(k); } int hed[2*N],cnt; struct EG { int to,nxt; }e[2*N]; void ae(int f,int t) { e[++cnt].to = t; e[cnt].nxt = hed[f]; hed[f] = cnt; } void dfs(int u) { tin[u]=++tim;pla[tim]=u; for(int j=hed[u];j;j=e[j].nxt)dfs(e[j].to); tout[u]=tim; } void build() { for(int i=2;i<=tot;i++) ae(p[i].pre,i); dfs(1); } }sam; int ans[60050],ct; struct Pair { int l,r,id; }qu[60050]; bool cmp(Pair a,Pair b) { return a.r<b.r; } int f[2*N]; void up(int x,int d) { if(!x)return ; while(x<=200000)f[x]+=d,x+=(x&(-x)); } int down(int x) { if(!x)return 0; int ret = 0; while(x)ret+=f[x],x-=(x&(-x)); return ret; } int las[10050]; int main() { scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) { scanf("%s",s+1); int len = strlen(s+1); sam.res(); for(int j=1;j<=len;j++) sam.insert(ic(s[j]),i); } sam.build(); for(int i=1;i<=q;i++) { scanf("%s",s+1); int len = strlen(s+1); int u = 1; for(int j=1;j<=len&&u;j++) u=sam.p[u].trs[ic(s[j])]; if(u) { ct++; qu[ct].l = tin[u]; qu[ct].r = tout[u]; qu[ct].id = i; } } sort(qu+1,qu+1+ct,cmp); for(int k=1,i=1;i<=tim;i++) { for(int j=0;j<sam.p[pla[i]].v.size();j++) { up(i,1); up(las[sam.p[pla[i]].v[j]],-1); las[sam.p[pla[i]].v[j]]=i; } int tmp = down(i); for(;qu[k].r==i;k++) ans[qu[k].id] = tmp - down(qu[k].l-1); } for(int i=1;i<=q;i++) printf("%d ",ans[i]); return 0; }