对trie建SAM，询问串倒过来跑到的节点的|right|即为答案。

#include
     
      using namespace std;#define ll long long#define inf 1000000010#define N 2000010char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){	int x=0,f=1;char c=getchar();	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();	return x*f;}int n,m,trie[N][26],son[N][26],fail[N],len[N],size[N],tmp[N],id[N],q[N],cnt=1;char s[N];int ins(int c,int p){    int x=++cnt;len[x]=len[p]+1;size[x]=1;    while (!son[p][c]&&p) son[p][c]=x,p=fail[p];    if (!p) fail[x]=1;    else    {        int q=son[p][c];        if (len[p]+1==len[q]) fail[x]=q;        else        {            int y=++cnt;            len[y]=len[p]+1;            memcpy(son[y],son[q],sizeof(son[q]));            fail[y]=fail[q],fail[x]=fail[q]=y;            while (son[p][c]==q) son[p][c]=y,p=fail[p];        }    }    return x;}int run(char *s){	int n=strlen(s+1);	int k=1;for (int i=n;i>=1;i--) k=son[k][s[i]-'A'];	return k;}signed main(){#ifndef ONLINE_JUDGE	freopen("a.in","r",stdin);	freopen("a.out","w",stdout);#endif	n=read(),m=read();	for (int i=1;i<=n;i++)	{		char c=getc();int x=read();		trie[x][c-'A']=i;	}	int head=0,tail=1;q[1]=0;id[0]=1;	do	{		int x=q[++head];		for (int i=0;i<26;i++)		if (trie[x][i])		{			q[++tail]=trie[x][i];			id[q[tail]]=ins(i,id[x]);		}	}while (head
      
       =2;i--) size[fail[q[i]]]+=size[q[i]];	while (m--)	{		scanf("%s",s+1);		printf("%d\n",size[run(s)]);	}	return 0;	//NOTICE LONG LONG!!!!!}