#include<bits/stdc++.h>
using namespace std;
char S[2000005];string s,t[100005];
int len[2000005],num[1000005],tr[1000005][26],n,m,nxt[1000005],in[1000005];
int val[1000005],val2[1000005],tot,h[4][1000005],p[2][1000005];
const int mod1=1000000007,mod2=1000000009;
void Manacher()
{
	S[0]='@';
	for(int i=1;i<=n;i++)S[2*i-1]='#',S[2*i]=s[i-1];
	S[2*n+1]='#';S[2*n+2]='%';
	int l=0,r=0;
	for(int i=1;i<=2*n+1;i++)
	{
		if(l&&r)len[i]=min(len[l+r-i],r-i);
		while(S[i-len[i]-1]==S[i+len[i]+1])len[i]++;
		if(i+len[i]>r){l=i-len[i];r=i+len[i];}
		num[(i-len[i]+1)/2]++;num[i/2+1]--;
	}
	for(int i=1;i<=n;i++)num[i]+=num[i-1],cout<<num[i]<<' ';cout<<'\n';
}
void ins(string s)
{
	int u=0,len=s.length();
	for(int i=0;i<len;i++)
	{
		int c=s[i]-'a';
		if(!tr[u][c])tr[u][c]=++tot;
		u=tr[u][c];
	}
}
void build()
{
	queue<int>q;
	for(int i=0;i<26;i++)if(tr[0][i])q.push(tr[0][i]);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=0;i<26;i++)
		{
			if(tr[u][i])nxt[tr[u][i]]=tr[nxt[u]][i],in[nxt[tr[u][i]]]++,q.push(tr[u][i]);
			else tr[u][i]=tr[nxt[u]][i];
		}
	}
}
void search(string s)
{
	int u=0;
	for(int i=0;i<n;i++)
	{
		int c=s[i]-'a';
		u=tr[u][c];
		val[u]++;
		if(i+2<=n)val2[u]+=num[i+2];
	}
}
void topo()
{
	queue<int>q;
	for(int i=0;i<=tot;i++)if(!in[i])q.push(i);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		in[nxt[u]]--;val[nxt[u]]+=val[u];val2[nxt[u]]+=val2[u];
		if(!in[nxt[u]])q.push(nxt[u]);
	}
}
int query(int x,int l,int r)
{
	int mod=(x%2==0?mod1:mod2);
	if(x<=1)return (h[x][r]-(l==0?0:1ll*h[x][l-1]*p[x][r-l+1]%mod)+mod)%mod;
	else return (h[x][l]-1ll*h[x][r+1]*p[x-2][r-l+1]%mod+mod)%mod;
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m>>s;reverse(s.begin(),s.end());
	Manacher();
	for(int i=1;i<=m;i++)
	{
		cin>>t[i];
		ins(t[i]); 
	}
	build();search(s);topo();
	for(int i=1;i<=m;i++)
	{
		int u=0,len=t[i].length();
		for(int j=0;j<len;j++)
		{
			int c=t[i][j]-'a';
			u=tr[u][c];
		}
		int res=val2[u];p[0][0]=p[1][0]=1;h[2][len]=h[3][len]=0;
		for(int j=0;j<len;j++)
		{
			h[0][j]=(j?(1ll*h[0][j-1]*131%mod1+t[i][j])%mod1:t[i][j]);
			h[1][j]=(j?(1ll*h[1][j-1]*131%mod2+t[i][j])%mod2:t[i][j]);
			p[0][j+1]=1ll*p[0][j]*131%mod1;
			p[1][j+1]=1ll*p[1][j]*131%mod2;
		}
		for(int j=len-1;j>=0;j--)
		{
			h[2][j]=(j<len-1?(1ll*h[2][j+1]*131%mod1+t[i][j])%mod1:t[i][j]);
			h[3][j]=(j<len-1?(1ll*h[3][j+1]*131%mod2+t[i][j])%mod2:t[i][j]);
		}
		u=0;
		for(int j=0;j<len;j++)
		{
			int c=t[i][j]-'a';
			u=tr[u][c];//cout<<u<<' '<<val[u]<<' '<<val2[u]<<'\n';
			///cout<<j+1<<' '<<(j+len)/2<<' '<<(j+len+1)/2<<' '<<len-1<<'\n'; 
			if(query(0,j+1,(j+len)/2)==query(2,(j+len+1)/2,len-1)&&query(1,j+1,(j+len)/2)==query(3,(j+len+1)/2,len-1))res+=val[u];
		}
		cout<<res<<'\n';
	}
	return 0;
}