显然答案等于模式串 si 和模板串的每一个后缀的匹配长度之和.(这里忽略了匹配成功的情况, 那种情况只需要额外特判一些东西.)
显然可以用线段树合并维护出 right 集合.
按照要求查询即可.
- #include<iostream>
- #include<cctype>
- #include<cstdio>
- #include<cstring>
- #include<string>
- #include<cmath>
- #include<ctime>
- #include<cstdlib>
- #include<algorithm>
- #define N 330000
- #define L 300000
- #define M 8800000
- #define eps 1e-7
- #define inf 1e9+7
- #define db double
- #define ll long long
- #define ldb long double
- using namespace std;
- inline int read()
- {
- char ch=0;
- int x=0,flag=1;
- while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}
- while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
- return x*flag;
- }
- char ch[N];
- int root=1,size=1,last=1;
- struct node{int len,pos,link,nxt[10];}s[N];
- void extend(int k)
- {
- int cur=++size,p=last;
- last=cur;s[cur].len=s[p].len+1;s[cur].pos=s[cur].len-1;
- while(p&&!s[p].nxt[k])s[p].nxt[k]=cur,p=s[p].link;
- if(!p){s[cur].link=root;return;}
- int q=s[p].nxt[k];
- if(s[q].len==s[p].len+1)s[cur].link=q;
- else
- {
- int clone=++size;
- s[clone]=s[q];s[clone].len=s[p].len+1;
- while(p&&s[p].nxt[k]==q)s[p].nxt[k]=clone,p=s[p].link;
- s[q].link=s[cur].link=clone;
- }
- }
- struct Segment_Tree
- {
- #define lson lc[o]
- #define rson rc[o]
- #define mid ((l+r)>>1)
- int tot,lc[M],rc[M],sumv[M];
- int merge(int x,int y)
- {
- if(!x||!y)return x|y;
- int o=++tot;
- lson=merge(lc[x],lc[y]);
- rson=merge(rc[x],rc[y]);
- sumv[o]=sumv[lson]+sumv[rson];
- return o;
- }
- void optadd(int &o,int l,int r,int k)
- {
- if(!o)o=++tot;
- if(l==r){sumv[o]++;return;}
- if(k<=mid)optadd(lson,l,mid,k);
- else optadd(rson,mid+1,r,k);
- sumv[o]=sumv[lson]+sumv[rson];
- }
- int query(int o,int l,int r,int ql,int qr)
- {
- if(ql<=l&&r<=qr)return sumv[o];
- int ans=0;
- if(ql<=mid)ans+=query(lson,l,mid,ql,qr);
- if(qr>mid)ans+=query(rson,mid+1,r,ql,qr);
- return ans;
- }
- }T;
- int f[N],rt[N];
- bool cmp(int a,int b){return s[a].len>s[b].len;}
- int main()
- {
- int n=read();scanf("%s",ch);
- for(int i=0;i<n;i++)extend(ch[i]-'0'),T.optadd(rt[last],0,n,i);
- for(int i=1;i<=size;i++)f[i]=i;sort(f+1,f+size+1,cmp);
- for(int i=1;i<size;i++) rt[s[f[i]].link]=T.merge(rt[s[f[i]].link],rt[f[i]]);
- int m=read();
- for(int o=1;o<=m;o++)
- {
- scanf("%s",ch);
- int x=root,len=strlen(ch),p=inf,now=0;ll ans=0;
- for(int i=0;i<len;i++)
- {
- int k=ch[i]-'0';
- if(s[x].nxt[k])x=s[x].nxt[k],now++;
- else
- {
- while(x&&!s[x].nxt[k])x=s[x].link;
- if(!x){x=root;now=0;continue;}
- else now=s[x].len+1,x=s[x].nxt[k];
- }
- }
- if(now==len)p=s[x].pos-len+1;
- x=root;now=0;
- ans+=T.query(rt[x],0,n,0,min(n,p));
- for(int i=0;i<len-1;i++)
- {
- int k=ch[i]-'0';
- if(s[x].nxt[k])x=s[x].nxt[k],now++;
- else
- {
- while(x&&!s[x].nxt[k])x=s[x].link;
- if(!x){x=root;now=0;continue;}
- else now=s[x].len+1,x=s[x].nxt[k];
- }
- if(i+1==now)ans+=T.query(rt[x],0,n,0,min(n,p+i));
- }
- printf("%lld\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2908890.html