代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int L[1000001],start[1000001],eNd[1000001],top=1;
int cnt,c[4000001],n,Q,a[4000001],Nxt[2000001],End[2000001];
int head[2000001],nxt[4000001],b[4000001],k,dfn[2000001],now,pos[2000001],mx[2000001];
int pre[2000001],tag[2000001];
long long ans[2000001];
inline void push(int s,int t){nxt[++k]=head[s],head[s]=k,b[k]=t;}
void update(int ind,int i){a[ind]=i;for(;ind<=n;ind+=ind&-ind)c[ind]=i;}
int query(int x,int y){static int ans;ans=0;while(y>=x){ans=max(a[y],ans);for(--y;y-(y&-y)>=x;y-=y&-y)ans=max(ans,c[y]);}return ans;}
int que(int x){
	if(tag[x]==now)return pre[x];
	if(dfn[x]<=dfn[pos[now]]&&mx[x]>=dfn[pos[now]])return (tag[x]=pre[x]=now);
	if(tag[x]==now-1)return (tag[x]=now,pre[x]);
	tag[x]=now;
	return pre[x]=query(dfn[x],mx[x]);
}
struct SAM{
    int son[2000001][26],fa[2000001],len[2000001],last,cnt;
    inline void clear(){last=cnt=1;memset(son[1],0,sizeof son[1]);}
    inline int add(int x){
        static int p;p=last;
        len[last=++cnt]=len[p]+1;
        memset(son[last],0,sizeof son[last]);
        for(;p&&!son[p][x];p=fa[p])son[p][x]=cnt;
        if(!p){fa[last]=1;return len[last];}
        static int q;q=son[p][x];
        if(len[q]==len[p]+1){fa[last]=q;return len[last]-len[q];}
        len[++cnt]=len[p]+1;
        fa[cnt]=fa[q];fa[q]=fa[last]=cnt;
        memcpy(son[cnt],son[q],sizeof son[cnt]);
        for(;son[p][x]==q;p=fa[p])son[p][x]=cnt;
        return len[last]-len[cnt];
    }
    void dfs(int x){
    	if(dfn[x])++now,dfn[x]=now;
    	else dfn[x]=now+1;
		for(int i=head[x];i;i=nxt[i])dfs(b[i]);
		mx[x]=now;
	}
    void settree(){for(int i=2;i<=cnt;i++)push(fa[i],i);dfs(1);}
}S,T;
char str[1000001];
void write(long long x){
	if(x>9)write(x/10);
	putchar((x%10)+'0');
}
int read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x;
}
int main(){
//	freopen("name.in","r",stdin);
//	freopen("name.out","w",stdout);
    scanf("%s",str+1);
    n=strlen(str+1);
    S.clear();
    for(register int i=1;i<=n;++i)S.add(str[i]-'a'),pos[i]=S.last,dfn[S.last]=1;
    S.settree();
    Q=read();
    for(int i=1,l,r;i<=Q;i++){
    	start[i]=top;
    	scanf("%s",str+top);
    	while(str[top])++top;
    	eNd[i]=top;
    	L[i]=read();
    	r=read();
    	Nxt[i]=End[r];
    	End[r]=i;
	}
	for(register int i=1;i<=n;++i){
		now=i;
		update(dfn[pos[i]],i);
		for(int m=End[i];m;m=Nxt[m]){
			int cnt=1,length=0,l=L[m];
			long long &A=ans[m];
			T.clear();
			for(register int j=start[m];j<eNd[m];++j){
				static int nExt,x;
				x=str[j]-'a';
				nExt=S.son[cnt][x];
	            if(l+length>i)length=i-l;
	            while(cnt!=1&&length<=S.len[S.fa[cnt]])cnt=S.fa[cnt];
	            while(cnt){
	            	static int tem;tem=que(nExt)-l;
	            	if(tem>=length)break;
	                if(!length){cnt=0;break;}
	                length=tem;
	                if(length<=S.len[S.fa[cnt]])cnt=S.fa[cnt],nExt=S.son[cnt][x],length=S.len[cnt];
	                else break;
	                if(!cnt)break;
	            }
	            if(!cnt)cnt=1,length=0;
	            else ++length,cnt=nExt;
	            A+=min(j-start[m]-length+1,T.add(x));
			}
		}
	}
	for(int i=1;i<=Q;i++)write(ans[i]),putchar('\n');
}

评测结果