传送门
人菜常数大系列
先考虑 68 68 68分的做法 答案就是 T T T的本质不同子串个数 − - − T T T和 S S S的公共子串 对 T T T建一个 S a m Sam Sam统计第一部分 第二部分就只需要 T T T在 S S S上跑,维护一下当前最长匹配长度和判重就可以了
考虑当 l = ̸ r l=\not r l≠r的时候 我们就需要知道在某一个区间有没有出现当前匹配的串 假设当前匹配长度为 x x x,我们当前在 S a m Sam Sam匹配到 p p p点 我们就需要知道 p p p的 e n d p o s endpos endpos是否有在 [ l + x , r ] [l+x,r] [l+x,r]内的
先单数合并维护,每次暴力查询就是了 但是不能失配就跳 f a i l fail fail,每次只能将匹配长度 − 1 -1 −1
#include<bits/stdc++.h> using namespace std; const int RLEN=1<<20|1; inline char gc(){ static char ibuf[RLEN],*ib,*ob; (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin)); return (ib==ob)?EOF:*ib++; } #define gc getchar inline int read(){ char ch=gc(); int res=0,f=1; while(!isdigit(ch))f^=ch=='-',ch=gc(); while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc(); return f?res:-res; } inline void readstring(char *s){ int len=0;char c; while(isspace(c=gc())); while(s[len++]=c,!isspace(c=gc())&&c!=EOF); } #define pii pair<int,int> #define fi first #define se second #define re register #define pb push_back #define ll long long inline void file(){ #ifdef Stargazer freopen("lx.cpp","r",stdin); #endif } int n,m; const int N=1000005; namespace Seg{ int totn,rt[N*25],siz[N*25],lc[N*25],rc[N*25]; #define mid ((l+r)>>1) inline void update(int &u,int l,int r,int p){ if(!u)u=++totn;siz[u]++; if(l==r)return; if(p<=mid)update(lc[u],l,mid,p); else update(rc[u],mid+1,r,p); } inline void merge(int &u,int r1,int r2){ if(!r1||!r2){u=r1+r2;return;} u=++totn,siz[u]=siz[r1]+siz[r2]; merge(lc[u],lc[r1],lc[r2]); merge(rc[u],rc[r1],rc[r2]); } inline int query(int u,int l,int r,int st,int des){ if(des<st)return 0; if(st<=l&&r<=des)return siz[u]; int res=0; if(st<=mid)res+=query(lc[u],l,mid,st,des); if(mid<des)res+=query(rc[u],mid+1,r,st,des); return res; } } using namespace Seg; int mx[N]; struct Sam{ int fa[N],len[N],pos[N],last,tot; map<int,int> nxt[N]; inline void clear(){ for(int i=1;i<=tot;i++)fa[i]=len[i]=pos[i]=0,nxt[i].clear(); last=tot=1; } inline int insert(int c,int i){ int cur=++tot,p=last;last=cur; len[cur]=len[p]+1,pos[cur]=i; for(;p&&!nxt[p][c];p=fa[p])nxt[p][c]=cur; if(!p)fa[cur]=1; else{ int q=nxt[p][c]; if(len[q]==len[p]+1)fa[cur]=q; else{ int clo=++tot;nxt[clo]=nxt[q]; fa[clo]=fa[q],len[clo]=len[p]+1,pos[clo]=pos[q]; for(;p&&nxt[p][c]==q;p=fa[p])nxt[p][c]=clo; fa[q]=fa[cur]=clo; } }return cur; } int cnt[N],p[N]; inline void build(){ for(int i=1;i<=tot;i++)cnt[i]=0; for(int i=1;i<=tot;i++)cnt[len[i]]++; for(int i=1;i<=tot;i++)cnt[i]+=cnt[i-1]; for(int i=1;i<=tot;i++)p[cnt[len[i]]--]=i; for(int i=tot;i;i--){ int u=p[i],f=fa[u]; merge(rt[f],rt[f],rt[u]); } // cout<<query(rt[1],1,n,1,n)<<'\n'; } inline void getans(char *s,int le,int l,int r){ int p=1,now=0; for(int i=1;i<=le;i++){ int c=s[i]-'a'; if(nxt[p][c]&&query(rt[nxt[p][c]],1,n,l+now,r)) now++,p=nxt[p][c]; else{ while(p&&(!nxt[p][c]||!query(rt[nxt[p][c]],1,n,l+now,r))){ if(!now){p=0;break;} now--; if(now==len[fa[p]])p=fa[p]; } if(!p)p=1,now=0; else now++,p=nxt[p][c]; } mx[i]=now; } } inline ll ask(){ ll res=0; for(int i=2;i<=tot;i++) res+=max(0,min(mx[pos[i]],len[i])-len[fa[i]]); return res; } inline ll calc(){ ll res=0; for(int i=1;i<=tot;i++)res+=len[i]-len[fa[i]]; return res; } }A,B; char s[N]; int main(){ A.clear(); scanf("%s",s+1); n=strlen(s+1),m=read(); for(int i=1;i<=n;i++)update(rt[A.insert(s[i]-'a',i)],1,n,i); A.build(); for(int i=1;i<=m;i++){ scanf("%s",s+1);B.clear(); int len=strlen(s+1); for(int j=1;j<=len;j++)B.insert(s[j]-'a',j); int l=read(),r=read(); A.getans(s,len,l,r); cout<<B.calc()-B.ask()<<'\n'; } }