代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
char s[1<<21],ss[1<<19];
int ps[1<<17],rnk[1<<22],sa[1<<21],tp[1<<21],c[1<<21],y='z',len[1<<17];
int st[22][1<<21],t,rt[1<<21],m,n,l[1<<17],r[1<<17],fnd,pos[1<<19];
struct segTree{
	int a[1<<24],L[1<<24],R[1<<24],tot;
	void ins(int x,int p,int tl=1,int tr=t){
		if(tl==tr){a[++tot]=a[p]+1;return;}
		int mid=tl+tr>>1;
		if(x<=mid)ins(x,L[p],tl,mid),R[++tot]=R[p],L[tot]=tot-1;
		else ins(x,R[p],mid+1,tr),L[++tot]=L[p],R[tot]=tot-1;
		a[tot]=a[L[tot]]+a[R[tot]];
	}
	void qry(int l,int r,int rt1,int rt2,int tl=1,int tr=t){
		if(l>r||a[rt1]==a[rt2]||fnd)return;
		if(l<=tl&&tr<=r){fnd=1;return;}
		int mid=tl+tr>>1;
		if(l<=mid)qry(l,r,L[rt1],L[rt2],tl,mid);
		if(r>mid&&!fnd)qry(l,r,R[rt1],R[rt2],mid+1,tr);
		return;
	}
}tr;
void tsort(int i){
	memset(c,0,sizeof c);int t=0;
	for(int j=1;j<=i;j++)tp[++t]=n-i+j;
	for(int j=1;j<=n;j++)c[rnk[j]]++,sa[j]>i&&(tp[++t]=sa[j]-i);
	for(int j=1;j<=y;j++)c[j]+=c[j-1];
	for(int j=n;j;j--)sa[c[rnk[tp[j]]]--]=tp[j];
}
void Sort(){
	for(int i=1;i<=n;i++)sa[i]=i,rnk[i]=s[i];
	tsort(0);
	for(int i=1;i==1 || y<n;i*=2){
		tsort(i);y=0;
		for(int j=1;j<=n;tp[sa[j++]]=y)
			y+=rnk[sa[j]]!=rnk[sa[j-1]]||rnk[sa[j]+i]!=rnk[sa[j-1]+i];
		memcpy(rnk,tp,sizeof tp);
	}
}
int qryL(int p,int t){
	for(int k=19;~k;k--)if(p>1<<k&&st[k][p-(1<<k)]>=t)p-=1<<k;
	return p;
}
int qryR(int p,int t){
	for(int k=19;~k;k--)if(p+(1<<k)<=n&&st[k][p]>=t)p+=1<<k;
	return p;
}
int rmq(int l,int r){int k=log2(r-l);return min(st[k][l],st[k][r-(1<<k)]);}
int main(){
	scanf(" %s",s+1);n=t=strlen(s+1);
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		s[++n]=y+1;scanf(" %s",ss);
		strcpy(s+n+1,ss);
		ps[i]=n+1,n+=len[i]=strlen(ss);
		scanf("%d%d",l+i,r+i);
	}
	s[++n]=++y;Sort();
	for(int i=1,k=0;i<=n;st[0][rnk[i++]-1]=k)
		for(k&&k--;s[i+k]==s[sa[rnk[i]-1]+k];k++);
	for(int i=1;(1<<i)<=n;i++)
		for(int j=1;j+(1<<i)<=n+1;j++)
			st[i][j]=min(st[i-1][j],st[i-1][j+(1<<i-1)]);
	for(int i=1;i<=n;i++)
		{if(sa[i]<=t)tr.ins(sa[i],rt[i-1]);rt[i]=tr.tot;}
	for(int i=1;i<=m;i++){
		struct st{int x,y;};basic_string<st> s;ll ans=0;
		for(int j=0;j<len[i];j++)s+={rnk[ps[i]+j],j};
		sort(s.begin(),s.end(),[](st a,st b){return a.x<b.x;});
		for(int j=0;j<len[i];j++)pos[s[j].y]=j;
		for(int j=0,k=1;j<len[i];j++){
			if(k>1)k--;int p=rnk[ps[i]+j],L;
			for(;fnd=0,tr.qry(l[i],r[i]-k+1,rt[qryL(p,k)-1],rt[qryR(p,k)]),fnd;k++);
			L=!pos[j]?0:rmq(s[pos[j]-1].x,p);
			ans+=len[i]-j-max(L,k-1);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

评测结果