代码

//by yjz
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<deque>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<set>
#include<utility>
#include<vector>

using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#define bged(v) (v).begin(),(v).end()
#define foreach(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
typedef long long ll;
const int Imx=2147483647;
const ll Lbig=2e18;
const int mod=1e9+7;
ll qpow(ll x,ll k){return k==0?1:1ll*qpow(1ll*x*x%mod,k>>1)*(k&1?x:1)%mod;}
const int maxn=2000111;
struct SGT
{
	struct node
	{
		int v,tl,tr;
		node(int V=0,int Tl=0,int Tr=0){v=V;tl=Tl;tr=Tr;}
	}a[maxn*20];
	int tot;
	void init()
	{
		tot=0;
		a[0]=node(0,0,0);
	}
	int newnode(int q)
	{
		int p=++tot;
		a[p]=node(a[q].v,a[q].tl,a[q].tr);
		return p;
	}
	int modify(int x,int l,int r,int q)
	{
		int p=newnode(q);
		a[p].v++;
		if(l==r)return p;
		int m=l+r>>1;
		if(x<=m)a[p].tl=modify(x,l,m,a[q].tl);
		else a[p].tr=modify(x,m+1,r,a[q].tr);
		return p;
	}
	int query(int x,int y,int l,int r,int p)
	{
		if(x<=l&&r<=y)return a[p].v;
		int m=l+r>>1,ret=0;
		if(x<=m)ret+=query(x,y,l,m,a[p].tl);
		if(m<y)ret+=query(x,y,m+1,r,a[p].tr);
		return ret;
	}
}sgt;
int rt[maxn];
char s[maxn];
int N,pos[maxn];
int n,m;
int b[maxn],sa[maxn],nsa[maxn],rk[maxn],nrk[maxn];
int lcp[maxn],tab[21][maxn],lg2[maxn];
int ql[maxn],qr[maxn];
void makeb(int N)
{
	memset(b,0,sizeof(b));
	for(int i=1;i<=N;i++)b[rk[i]]++;
	for(int i=1;i<=max(256,N);i++)b[i]+=b[i-1];
}
#define get_pp(x) MP(rk[x],x+k<=N?rk[x+k]:-1)
void construct()
{
	for(int i=1;i<=N;i++)rk[i]=s[i];
	makeb(N);
	for(int i=N;i>=1;i--)sa[b[rk[i]]--]=i;
	for(int k=1;k<N;k<<=1)
	{
		makeb(N);
		for(int i=N;i>=1;i--)if(sa[i]>k)nsa[b[rk[sa[i]-k]]--]=sa[i]-k;
		for(int i=N;i>=1;i--)if(sa[i]>N-k)nsa[b[rk[sa[i]]]--]=sa[i];
		nrk[nsa[1]]=1;
		for(int i=2;i<=N;i++)nrk[nsa[i]]=nrk[nsa[i-1]]+(get_pp(nsa[i-1])<get_pp(nsa[i]));
		swap(rk,nrk);
		swap(sa,nsa);
	}
	for(int i=1;i<=N;i++)rk[sa[i]]=i;
	int h=0;
	for(int i=1;i<=N;i++)
	{
		if(h>0)h--;
		if(rk[i]==1)continue;
		int j=sa[rk[i]-1];
		while(i+h<=N&&j+h<=N&&s[i+h]==s[j+h])h++;
		lcp[rk[i]-1]=h;
	}
	for(int i=2;i<maxn;i++)lg2[i]=lg2[i>>1]+1;
	for(int i=1;i<=N;i++)tab[0][i]=lcp[i];
	for(int i=1;i<=20;i++)
	{
		for(int j=1;j<=N-(1<<i)+1;j++)
		{
			tab[i][j]=min(tab[i-1][j],tab[i-1][j+(1<<i-1)]);
		}
	}
	rt[0]=0;
	for(int i=1;i<=n;i++)
	{
		rt[i]=sgt.modify(rk[i],1,N,rt[i-1]);
	}
}
int query_lcp_rk(int x,int y)
{
	if(x==y)return N-sa[x]+1;
	int t=lg2[y-x];
	return min(tab[t][x],tab[t][y-(1<<t)]);
}
int query_lcp(int x,int y)
{
	x=rk[x];y=rk[y];
	return query_lcp_rk(min(x,y),max(x,y));
}
bool check(int s,int l,int px,int py)
{
	int x=rk[s];
	int pl=x;
	for(int t=20;t>=0;t--)
	{
		if(pl>(1<<t)&&tab[t][pl-(1<<t)]>=l)
		{
			pl-=1<<t;
		}
	}
	int pr=x;
	for(int t=20;t>=0;t--)
	{
		if(pr+(1<<t)<=N&&tab[t][pr]>=l)
		{
			pr+=1<<t;
		}
	}
	return sgt.query(pl,pr,1,N,rt[py])-sgt.query(pl,pr,1,N,rt[px-1])>0;
}
ll query(int x)
{
	static int ban[maxn];
	int len=pos[x+1]-pos[x];
	vector<int> v;
	for(int i=0;i<len;i++)v.PB(rk[i]);
	sort(v.begin(),v.end());
	ban[sa[v[0]]-pos[x]]=0;
	for(int i=1;i<len;i++)
	{
		ban[sa[i]-pos[x]]=query_lcp_rk(v[i-1],v[i]);
	}
	int l=0;
	ll ans=0;
	for(int i=0;i<len;i++)
	{
		if(l>0)l--;
		while(i+l<len&&l<=qr[x]-ql[x]&&check(pos[x]+i,l+1,ql[x],qr[x]-l))l++;
		ans+=len-i-max(ban[i],l);
	}
	return ans;
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	N=n;
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		pos[i]=N+1;
		scanf("%s",s+N+1);
		int l=strlen(s+N+1);
		N+=l;
		scanf("%d%d",&ql[i],&qr[i]);
	}
	pos[m+1]=N+1;
	construct();
	for(int i=1;i<=m;i++)
	{
		ll ans=query(i);
		printf("%lld\n",ans);
	}
	return 0;
}

评测结果