代码

/* 
 * Author: $%U%$
 * Time: $%Y%$-$%M%$-$%D%$ $%h%$:$%m%$:$%s%$
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(ll i=(a);i<=(b);i++)
#define per(i,a,b) for(ll i=(a);i>=(b);i--)
#define re(i,a,b) for(ll i=(a);i<(b);i++)
#define pe(i,a,b) for(ll i=(a);i>(b);i--)
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline void read(T& r) {
	r=0;bool w=0; char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9') r=r*10+(ch^48), ch=getchar();
	r=w?-r:r;
}
template <typename T>
inline void readupp(T& r){
	r=0;
	char ch=getchar();
	while(ch>'Z'||ch<'A')ch=getchar();
	r=ch;
}
template <typename T>
inline void readlow(T& r){
	r=0;
	char ch=getchar();
	while(ch>'z'||ch<'a')ch=getchar();
	r=ch;
}
template <typename T>
inline void readdig(T& r){
	r=0;
	char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	r=ch-'0';
}
template <typename T>
inline void readvisi(T& r){
	r=0;
	char ch=getchar();
	while(ch>126||ch<33)ch=getchar();
	r=ch;
}
template <typename T>
inline ll readlowstr(T& r){
	ll n=0;
	char ch=getchar();
	while(ch>'z'||ch<'a')ch=getchar();
	while(ch<='z'&&ch>='a')r[++n]=ch-'a',ch=getchar();
	return n;
}
template <typename T>
inline ll readuppstr(T& r){
	ll n=0;
	char ch=getchar();
	while(ch>'Z'||ch<'A')ch=getchar();
	while(ch<='Z'&&ch>='A')r[++n]=ch-'A',ch=getchar();
	return n;
}
template <typename T>
inline ll readdigstr(T& r){
	ll n=0;
	char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch<='9'&&ch>='0')r[++n]=ch-'0',ch=getchar();
	return n;
}
template <typename T>
inline ll readvisistr(T& r){
	ll n=0;
	char ch=getchar();
	while(ch>126||ch<33)ch=getchar();
	while(ch<=126&&ch>=33)r[++n]=ch,ch=getchar();
	return n;
}
const ll MOD=998244353;
ll gcd(ll A,ll B){return B?gcd(B,A%B):A;}
template<typename T>
void chkmax(T&A,T B){if(A<B)A=B;}
template<typename T>
void chkmin(T&A,T B){if(A>B)A=B;}
template<typename T>
T Madd(T A,T B){return A+B>=MOD?A+B-MOD:A+B;}
template<typename T>
T Msub(T A,T B){return A-B<0?A-B+MOD:A-B;}
template<typename T>
void MODed(T &A){A%=MOD;A+=(A<0?MOD:0);}
ll pw(ll A,ll B){
	ll res=1;
	while(B){
		if(B&1)res=res*A%MOD;
		A=A*A%MOD;
		B>>=1;
	}
	return res;
}
void _FILE(string s){
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}
const ll N=1000003,M=3003,INF=2000000000000000007ll;
ll n,s[N];
struct node{
	int fa,len,ch[26];
};
struct sam{
	node nd[N*2];
	ll lst=1,cnt=1;
	void add(ll x){
		ll p=lst;
		cnt++;
		ll np=cnt;
		lst=cnt;
		nd[np].len=nd[p].len+1;
		while(p&&!nd[p].ch[x])nd[p].ch[x]=np,p=nd[p].fa;
		if(p==0){
			nd[np].fa=1;
			return;
		}
		ll q=nd[p].ch[x];
		if(nd[q].len==nd[p].len+1){
			nd[np].fa=q;
			return;
		}
		ll nq=++cnt;
		nd[nq]=nd[q];
		nd[q].fa=nq,nd[np].fa=nq;
		nd[nq].len=nd[p].len+1;
		while(p&&nd[p].ch[x]==q)nd[p].ch[x]=nq,p=nd[p].fa;
	}
	void clear(){
		rep(i,1,cnt)nd[i].fa=0,nd[i].len=0,memset(nd[i].ch,0,sizeof(nd[i].ch));
		cnt=1,lst=1;
	}
};
sam S,T;
vector<ll> e[N],f[N];
struct tnode{
	int lc,rc,val;
};
tnode tr[40000003];
ll rt[N];
ll Cnt=0;
void buildch(ll x){
	Cnt++;
	tr[x].lc=Cnt;
	Cnt++;
	tr[x].rc=Cnt;
}
void tadd(ll p,ll xl,ll xr,ll x,ll Val){
	if(xl>p||xr<p)return;
	if(xl==p&&xr==p){
		tr[x].val+=Val;
		return;
	}
	if(!tr[x].lc)buildch(x);
	ll o=(xl+xr)>>1;
	tadd(p,xl,o,tr[x].lc,Val);
	tadd(p,o+1,xr,tr[x].rc,Val);
	tr[x].val=tr[tr[x].lc].val+tr[tr[x].rc].val;
}
ll merge(ll x,ll y){
	if(x==0&&y==0)return 0;
	if(x==0)return y;
	if(y==0)return x;
	if(!tr[x].lc&&!tr[y].lc){
		Cnt++;
		tr[Cnt].val=tr[x].val+tr[y].val;
		return Cnt;
	}
	ll tmp=++Cnt;
	tr[tmp].lc=merge(tr[x].lc,tr[y].lc);
	tr[tmp].rc=merge(tr[x].rc,tr[y].rc);
	tr[tmp].val=tr[tr[tmp].lc].val+tr[tr[tmp].rc].val;
	return tmp;
}
ll query1(ll L,ll R,ll xl,ll xr,ll x){
	if(xl>R||xr<L)return 0;
	if(xl>=L&&xr<=R)return tr[x].val;
	if(!tr[x].lc)return 0;
	ll o=(xl+xr)>>1;
	return query1(L,R,xl,o,tr[x].lc)+query1(L,R,o+1,xr,tr[x].rc);
}
ll query2(ll xl,ll xr,ll x,ll p){
	if(tr[x].val<p)return -1;
	if(xl==xr)return xl;
	ll o=(xl+xr)>>1;
	if(tr[tr[x].lc].val>=p)return query2(xl,o,tr[x].lc,p);
	else return query2(o+1,xr,tr[x].rc,p-tr[tr[x].lc].val);
}
void dfs(ll u){
	re(i,0,e[u].size())dfs(e[u][i]);
	re(i,0,e[u].size())rt[u]=merge(rt[u],rt[e[u][i]]);
}
ll q,m,t[N],pre[N],fp[N];
void dfs2(ll u){
	re(i,0,f[u].size())dfs2(f[u][i]);
	re(i,0,f[u].size())fp[u]=min(fp[u],fp[f[u][i]]);
}
int main(){
    //_FILE("name");
	n=readlowstr(s);
	rep(i,1,n)S.add(s[i]);
	rep(i,2,S.cnt){
		e[S.nd[i].fa].push_back(i);
	}
	rep(i,1,S.cnt){
		Cnt++;
		rt[i]=Cnt;
	}
	ll o=1;
	rep(i,1,n){
		o=S.nd[o].ch[s[i]];
		tadd(i,1,n,rt[o],1);
	}
	dfs(1);
	read(q);
	rep(i,1,q){
		ll ql,qr;
		m=readlowstr(t);
		read(ql),read(qr);
		fill(pre+1,pre+m+1,0);
		ll p=1;
		rep(j,1,m){
			while(p&&!S.nd[p].ch[t[j]])p=S.nd[p].fa;
			ll uuu=min((ll)S.nd[p].len,pre[j-1]);
			if(S.nd[p].ch[t[j]])p=S.nd[p].ch[t[j]];
			else p=1;
			ll o1,o2,ooo;
			while(1){
				o1=query1(1,qr,1,n,rt[p]);
				if(o1==0)p=S.nd[p].fa;
				else{
					o2=query2(1,n,rt[p],o1);
					if(o2<ql){
						p=S.nd[p].fa;
					}
					else{
						ooo=S.nd[S.nd[p].fa].len+1;
						if(o2-ooo+1<ql){
							p=S.nd[p].fa;
						}
						else break;
					}
				}
			}
			pre[j]=min(min((ll)S.nd[p].len,o2-ql+1),uuu+1);
		}
		T.clear();
		rep(j,1,m)T.add(t[j]);
		ll ans=0;
		rep(j,1,T.cnt)f[j].clear();
		rep(j,2,T.cnt)f[T.nd[j].fa].push_back(j);
		ll w=1;
		fill(fp+1,fp+T.cnt+1,m+1);
		rep(j,1,m){
			w=T.nd[w].ch[t[j]];
			fp[w]=j;
		}
		dfs2(1);
		rep(j,2,T.cnt)ans+=max(0ll,(ll)T.nd[j].len-max((ll)pre[fp[j]],(ll)T.nd[T.nd[j].fa].len));
		printf("%lld\n",ans);
	}
	return 0;
}

评测结果