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

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

    第三行是一个整数m。

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

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

#include<bits/stdc++.h>typedef long long i64;const int N=2e5+77;int n,m;char s1[N];int nx[N][10],ch[N][10],l[N],fa[N],pv=1,ptr=1,lr[N][2],in[N],q[N],ql,qr,id[N][2],idp=0;int bit[N],bs[N],ws[N];void inc(int w){    for(++bs[w];w<=idp;w+=w&-w)++bit[w];}bool _=0;int sum(int w){    if(_)return bs[w];    int s=0;    for(;w;w-=w&-w)s+=bit[w];    return s;}void ins(int pos){    int x=s1[pos]-=‘0‘;    int p=pv,np=++ptr;    l[np]=l[p]+1;    while(p&&!nx[p][x])nx[p][x]=np,p=fa[p];    if(!p)fa[np]=1;    else{        int q=nx[p][x];        if(l[q]==l[p]+1)fa[np]=q;        else{            int nq=++ptr;            lr[nq][1]=n+1;            l[nq]=l[p]+1;            memcpy(nx[nq],nx[q],sizeof(nx[0]));            fa[nq]=fa[q];            fa[q]=fa[np]=nq;            while(p&&nx[p][x]==q)nx[p][x]=nq,p=fa[p];        }    }    ws[pos]=np;    lr[np][1]=n;    pv=np;}void dfs(int w){    id[w][0]=++idp;    for(int i=0;i<10;++i)if(ch[w][i])dfs(ch[w][i]);    id[w][1]=idp;}void mins(int&a,int b){if(a>b)a=b;}i64 as[50007];struct Q{    char*s;    int len,e,ID;    void match(){        int w=1,p=0;        for(int i=0;i<len&&w;++i){            int x=s[i]-‘0‘;            if(p==lr[w][1])p=lr[w=ch[w][x]][0];            else if(s1[++p]!=x)w=0;        }        e=w?p-len+1:n+1;    }    void cal(){        int w=1,p=0;        for(int i=0;i<len&&w;++i){            int x=s[i]-‘0‘;            if(p==lr[w][1])p=lr[w=ch[w][x]][0];            else if(s1[++p]!=x)w=0;            as[ID]+=sum(id[w][1])-sum(id[w][0]-1);        }        as[ID]+=e>n?n:e-1;    }    bool operator<(Q x)const{return e<x.e;}}qs[50007];char s2[5000007],*sp2=s2;int main(){    scanf("%d%s",&n,s1+1);    for(int i=n;i;--i)ins(i);    for(int i=1;i<=ptr;++i)++in[fa[i]];    for(int i=1;i<=ptr;++i)if(!in[i])q[++qr]=i;    in[1]=-1;    while(ql!=qr){        int w=q[++ql],f=fa[w];        if(!--in[f])q[++qr]=f;        lr[w][0]=lr[w][1]-l[w]+l[f]+1;        mins(lr[f][1],lr[w][0]-1);        ch[f][s1[lr[w][0]]]=w;    }    dfs(1);    scanf("%d",&m);    for(int i=0;i<m;++i){        scanf("%s",sp2);        qs[i].s=sp2;        qs[i].len=strlen(sp2);        qs[i].match();        qs[i].ID=i;        sp2+=qs[i].len+2;    }    std::sort(qs,qs+m);    int qp=0;    for(int i=1;i<=n;++i){        inc(id[ws[i]][0]);        for(;qp<m&&qs[qp].e==i;++qp)qs[qp].cal();    }    _=1;    for(int i=1;i<=idp;++i)bs[i]+=bs[i-1];    for(;qp<m;++qp)qs[qp].cal();    for(int i=0;i<m;++i)printf("%lld\n",as[i]);    return 0;}