代码

#include<bits/stdc++.h>
using namespace std;
const int A=1000005;
vector<int> g[A];
char str[A];
int len,lens,q,zzw,ls[A*40],rs[A*40],mx[A*40],root[A],tot,fl[A];
typedef long long ll;
void Insert(int &p,int l,int r,int x,int y){
	p=++tot,mx[p]=y;
	if(l==r)return ;
	int mid=(l+r)/2;
	if(x<=mid)Insert(ls[p],l,mid,x,y);
	else Insert(rs[p],mid+1,r,x,y);
}
int Merge(int p,int q,int l,int r){
	if(!p||!q)return p+q;
	if(l>r)return 0;
	int rr=++tot,mid=(l+r)/2;
	ls[rr]=Merge(ls[p],ls[q],l,mid),rs[rr]=Merge(rs[p],rs[q],mid+1,r);
	mx[rr]=max(mx[ls[rr]],mx[rs[rr]]);
	return rr;
}
int Query(int p,int l,int r,int x,int y){
	if((!p)||(x<=l&&r<=y))return mx[p];
	int mid=(l+r)/2,re=0;
	if(x<=mid)re=max(re,Query(ls[p],l,mid,x,y));
	if(mid<y)re=max(re,Query(rs[p],mid+1,r,x,y));
	return re;
}
struct SAM {
	int c[A][26],fa[A],len[A],lst,tot,w[A],rk[A],s[A];
	int Ins(int x,int ww) {
		int p=lst,now=++tot;
		memset(c[now],0,sizeof(c[now])),lst=now,w[now]=ww;
		len[now]=len[p]+1;
		for(; p&&!c[p][x]; p=fa[p])c[p][x]=now;
		if(!p)return fa[now]=1;
		int q=c[p][x];
		if(len[p]+1==len[q])return fa[now]=q;
		int nq=++tot;
		memcpy(c[nq],c[q],sizeof(c[q])),len[nq]=len[p]+1,fa[nq]=fa[q],fa[now]=fa[q]=nq;
		for(; p&&c[p][x]==q; p=fa[p])c[p][x]=nq;
		return 0;
	}
	void Clear(){
		tot=lst=1;
		memset(c[1],0,sizeof(c[1]));
	}
	void Make(){
		for(int i=1;i<=tot;i++)s[len[i]]++;
		for(int i=1;i<=tot;i++)s[i]+=s[i-1];
		for(int i=1;i<=tot;i++)if(w[i])Insert(root[i],1,lens,w[i],len[i]);
		for(int i=tot;i>=1;i--)rk[s[len[i]]--]=i;
		for(int i=tot,x;i>=1;i--)if(fa[x=rk[i]])root[fa[x]]=Merge(root[fa[x]],root[x],1,lens);
	}
	SAM(){
		Clear();
	}
}S,T;
void MakeS(){
	for(int i=2;i<=S.tot;i++)g[S.fa[i]].push_back(i);
	S.Make();
}
bool Has(int p,int w,int l,int r){
	if(!S.c[p][w])return 0;
	return Query(root[S.c[p][w]],1,lens,1,r)>=l;
}
int main() {
//	freopen("name18.in","r",stdin);
//	freopen("name.out","w",stdout);
	scanf("%s",str),lens=len=strlen(str);
	for(int i=0;i<len;i++)S.Ins(str[i]-'a',i+1);
	MakeS();
	scanf("%d",&q);
	while(q--){
		int L,R;
		scanf("%s%d%d",str+1,&L,&R),len=strlen(str+1),T.Clear();
		for(int i=1;i<=len;i++)T.Ins(str[i]-'a',i),fl[i]=T.len[T.fa[T.lst]];
		ll ans=0;
		for(int i=1,p=1,l=0;i<=len;i++){
			int w=str[i]-'a';
			while(1){
				if(Has(p,w,L+l,R)){
					p=S.c[p][w],l++;
					break;
				}
				if(!l)break;
				l--;
				if(l==S.len[S.fa[p]])p=S.fa[p];
			}
			if(l>fl[i])ans-=l-fl[i];
		}
		for(int i=1;i<=len;i++)ans+=i-fl[i];
		cout<<ans<<'\n';
	}
}

评测结果