代码

#include<bits/stdc++.h>
typedef long long ll;
char ibuf[1<<23],*ih=ibuf,obuf[1<<22],*oh=obuf;
inline void read(int&x){
	for(;!isdigit(*ih);++ih);
	for(x=0;isdigit(*ih);x=x*10+*ih++-48);
}
inline void readstr(char*c){
	for(;isspace(*ih);++ih);
	for(;!isspace(*ih);*c++=*ih++);*c=0;
}
inline void out(ll x){
	if(!x){*oh++='0';return;}
	static int buf[30];int xb=0;
	for(;x;x/=10)buf[++xb]=x%10;
	for(;xb;)*oh++=buf[xb--]|48;
}
const int N=1000005;
struct node{
	int l,r,sz;
}t[N*22];
int sz;
void ins(int x,int&y,int l,int r,int k){
	t[y=++sz]=t[x];++t[y].sz;
	if(l==r)return;int m=(l+r)>>1;
	if(k>m)ins(t[x].r,t[y].r,m+1,r,k);else ins(t[x].l,t[y].l,l,m,k);
}
bool query(int x,int y,int rl,int rr,int l,int r){
	if(rl==l && rr==r)return t[y].sz>t[x].sz;
	if(!y)return 0;
	int m=(rl+rr)>>1;
	if(r<=m)return query(t[x].l,t[y].l,rl,m,l,r);
		else if(l>m)return query(t[x].r,t[y].r,m+1,rr,l,r);
				else return query(t[x].l,t[y].l,rl,m,l,m) || query(t[x].r,t[y].r,m+1,rr,m+1,r);
}
char c[N];
struct SAM{
	int ch[N][26],pre[N],step[N],xb,n,wz[N],pos[N];
	inline void build(){
		int p,q,np,nq,lst=xb=1,i,x;
		readstr(c+1);memset(ch[1],0,104);
		for(i=1;c[i];++i){
			x=c[i]-'a';step[np=++xb]=step[p=lst]+1;
			memset(ch[np],0,104);
			for(;p && !ch[p][x];p=pre[p])ch[p][x]=np;
			if(p){
				q=ch[p][x];
				if(step[p]+1!=step[q]){
					step[nq=++xb]=step[p]+1;
					memcpy(ch[nq],ch[q],104);
					pre[nq]=pre[q];pre[q]=pre[np]=nq;
					for(;p && ch[p][x]==q;p=pre[p])ch[p][x]=nq;
				}else pre[np]=q;
			}else pre[np]=1;
			wz[pos[lst=np]=i]=np;
		}n=i-1;
	}
	int rt[N],id[N],ri[N],dfn[N],cn;
	std::vector<int>e[N];
	void dfs(int x){
		dfn[id[x]=++cn]=x;
		for(int i=0;i<e[x].size();++i)dfs(e[x][i]);
		ri[x]=cn;
	}
	inline void ini(){
		int i;
		for(i=1;i<=xb;++i)e[pre[i]].push_back(i);
		dfs(1);
		for(i=1;i<=cn;++i){
			rt[i]=rt[i-1];
			if(pos[dfn[i]])ins(rt[i],rt[i],1,n,pos[dfn[i]]);
		}		
	}
	int len[N];
	inline void wk(){
		ll ans=0;
		int i;static int a[N],b[N];
		for(i=1;i<=xb;++i)++a[step[i]];
		for(i=1;a[i];++i)a[i]+=a[i-1];
		for(i=1;i<=xb;++i)b[a[step[i]]--]=i;
		for(i=xb;i;--i){
			int x=step[b[i]]-step[pre[b[i]]];
			if(len[b[i]]>x)ans+=x,len[pre[b[i]]]=len[b[i]]-x;
				else ans+=len[b[i]];
		}
		for(i=1;i<=xb;++i)a[step[i]]=0;
		out(ans);*oh++='\n';
	}
/*
	char st[100];int w;
	void out(int x){//just for debug
		for(int i=1;i<=w;++i)putchar(st[i]);puts("");
		for(int i=0;i<26;++i)if(ch[x][i])st[++w]=i+'a',out(ch[x][i]),--w;
	}
*/
}S,T;
int Q,l,r,i;
int main(){
//	freopen("name.in","r",stdin);freopen("name.out","w",stdout);
	fread(ibuf,1,1<<23,stdin);
	S.build();S.ini();read(Q);
//	S.out(1);
	while(Q--){
		T.build();read(l);read(r);
		int u=1,x;
		memset(T.len+1,0,T.xb<<2);
		int le=0;
		for(i=1;i<=T.n;++i){
			x=c[i]-'a';
			for(;u>1 && !S.ch[u][x];u=S.pre[u]);
			if(le>S.step[u])le=S.step[u];
			if(!S.ch[u][x]){T.len[T.wz[i]]=i;continue;}u=S.ch[u][x];++le;
			for(;u>1 && !query(S.rt[S.id[u]-1],S.rt[S.ri[u]],1,S.n,l,r);u=S.pre[u]);
			if(le>S.step[u])le=S.step[u];
			T.len[T.wz[i]]=i-le;
		}
		T.wk();
	}
	fwrite(obuf,1,oh-obuf,stdout);
	return 0;
}

评测结果