第一行包含一个整数n(≤100000)。

第二行是长度为n的由0到9组成的字符串。

第三行是一个整数m。

接下来m≤5·10行，第i行是一个由0到9组成的字符串s，保证单行字符串长度小于等于10^5，所有字符串长度和小于等于3·10^6

输出m行，第i行表示第si和S匹配所比较的次数。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

typedef long long ll;

const int N=200010;

int n,m,tot,last,cnt;

char S[N],T[N];

int ch[N][10],mx[N],pre[N],p1[N],p2[N],mn[N],pos[N],qos[N],len[N],s[N],L[N],R[N],son[N][10],siz[N];

vector<int> q[N];

vector<int>::iterator it;

int f[N];

ll ans[N];

inline int extend(int x)

{

	int p=last,np=++tot;	last=np;

	mx[np]=mx[p]+1,siz[np]=1;

	for(;p&&!ch[p][x];p=pre[p])	ch[p][x]=np;

	if(!p)	ch[1][x]=np,pre[np]=1;

	else

	{

		int q=ch[p][x];

		if(mx[q]==mx[p]+1)	pre[np]=q;

		else

		{

			int nq=++tot;	mx[nq]=mx[p]+1,R[nq]=R[q]-(mx[q]-mx[p]-1);

			pre[nq]=pre[q],pre[np]=pre[q]=nq;

			memcpy(ch[nq],ch[q],sizeof(ch[q]));

			for(;p&&ch[p][x]==q;p=pre[p])	ch[p][x]=nq;

		}

	}

	return np;

}

void dfs(int x)

{

	p1[x]=++p2[0];

	for(int i=0,y;i<10;i++)	if((y=son[x][i]))	dfs(y),siz[x]+=siz[y],mn[x]=min(mn[x],mn[y]);

	p2[x]=p2[0];

}

inline void updata(int x)

{

	for(int i=x;i<=tot;i+=i&-i)	s[i]++;

}

inline int query(int x)

{

	int ret=0,i;

	for(i=x;i;i-=i&-i)	ret+=s[i];

	return ret;

}

int main()

{

	scanf("%d%s",&n,S);

	int i,j,x,y;

	memset(mn,0x3f,sizeof(mn));

	tot=last=1;

	for(i=n-1;i>=0;i--)	pos[i]=extend(S[i]-'0'),mn[pos[i]]=i,R[pos[i]]=n-1;

	for(i=2;i<=tot;i++)	L[i]=R[i]-(mx[i]-mx[pre[i]])+1,son[pre[i]][S[L[i]]-'0']=i;

	scanf("%d",&m);

	dfs(1);

	R[1]=-1;

	for(i=1;i<=m;i++)

	{

		scanf("%s",T),len[i]=strlen(T);

		for(x=1,j=y=0;j<len[i];j++)

		{

			if(y<=R[x])

			{

				if(S[y]==T[j])	y++;

				else	break;

			}

			else

			{

				if(son[x][T[j]-'0'])	x=son[x][T[j]-'0'],y=L[x]+1;

				else	break;

			}

		}

		qos[i]=x;

		if(j<len[i])

		{

			if(x==1)	ans[i]=n;

			else

			{

				ans[i]=n+1ll*siz[x]*min(mx[x]-mx[pre[x]],y-L[x]);

				for(x=pre[x];x!=1;x=pre[x])	ans[i]+=1ll*(mx[x]-mx[pre[x]])*siz[x];

			}

		}

		else

		{

			ans[i]=len[i]+mn[x];

			if(mn[x])	q[mn[x]-1].push_back(i);

		}

	}

	for(i=0;i<n;i++)

	{

		updata(p1[pos[i]]);

		for(it=q[i].begin();it!=q[i].end();it++)

		{

			for(j=pre[qos[*it]];j;j=pre[j])	ans[*it]+=1ll*(mx[j]-mx[pre[j]])*(query(p2[j])-query(p1[j]-1));

		}

	}

	for(i=1;i<=m;i++)	printf("%lld\n",ans[i]);

	return 0;

}