10pts 求卡常

#include<bits/stdc++.h>
#define endl '\n'
#define N 100006
#define M 5000006
using namespace std;
int n,q,e[N],trans[200];
string s,t,all;
struct ACAM {
	int tot,tr[M][6],fail[M],sum[M];
	int ecnt,head[M],to[M],nxt[M];
	inline void addedge(int u,int v){nxt[++ecnt]=head[u],to[ecnt]=v,head[u]=ecnt;}
	int insert(string s)
	{
		int u=0,ch;
		for(auto c:s)
		{
			ch=trans[c];
			if(!tr[u][ch])tr[u][ch]=++tot;
			u=tr[u][ch];
		}
		return u;
	}
	void build()
	{
		queue<int> q;
		for(int i=0;i<6;i++)
			if(tr[0][i])q.push(tr[0][i]);
		while(q.size())
		{
			int u=q.front(); q.pop();
			for(int i=0;i<6;i++)if(tr[u][i])
				fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]);
			else tr[u][i]=tr[fail[u]][i];
		}
		for(int i=1;i<=tot;i++)addedge(fail[i],i);
	}
	void dfs(int u){for(int i=head[u];i;i=nxt[i])dfs(to[i]),sum[u]+=sum[to[i]];}
	void add(string s)
	{
		int u=0,ret=0,ch;
		for(auto c:s)
			ch=trans[c],u=tr[u][ch],sum[u]++;
		dfs(0);
	}
}AM;
main()
{
	scanf("%d%d",&n,&q);
	trans['A']=0,trans['G']=1,trans['C']=2,trans['U']=3,trans['?']=4,trans['#']=5;
	for(int i=1;i<=n;i++)cin>>s,all=all+'?'+s+'#'+s;
	for(int i=1;i<=q;i++)
		cin>>s>>t,s=t+'#'+s,e[i]=AM.insert(s);
	AM.build(),AM.add(all);
	for(int i=1;i<=q;i++)printf("%d\n",AM.sum[e[i]]);
	return 0;
}