代码

#include<bits/stdc++.h>
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
namespace io
{
	int F()
	{
		 int F=1,n=0;
		 char ch;
		 while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		 ch=='-'?F=0:n=ch-'0';
		 while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		 return F?n:-n;
	}
	long long G()
	{
		 long long F=1,n=0;
		 char ch;
		 while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		 ch=='-'?F=0:n=ch-'0';
		 while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		 return F?n:-n;
	}
}
int R(int l,int r)
{
	return (rand()<<15|rand())%(r-l+1)+l;
}
struct sam;
struct edge
{
	sam* to;
	edge* next;
};
struct sam
{
	int len,at;
	sam* next[26];
	sam* fa;
	edge* fir;
	void clear()
	{
		memset(next,0,sizeof(next));
		fa=0;
		fir=0;
	}
};
template <int _n> struct Sam
{
	sam *pp,*pq,*last;
	sam m[_n+_n+3];
	edge e[_n+_n],*pe;
	Sam()
	{
		pp=m+1,pq=m+_n+1,last=m;
		pe=e;
	}
	void clear()
	{
		pp=m+1,pq=m+_n+1,last=m;
		pe=e;
		m->clear();
	}
	void insert(sam* a,sam* to)
	{
		*pe=(edge){to,a->fir};
		a->fir=pe++;
	} 
	sam* ext(int c,int pl)
	{
		sam* np=pp++;
		np->clear();
		np->at=pl;
		np->len=last->len+1;
		sam* p=last;
		for(;p&&!p->next[c];p=p->fa)p->next[c]=np;
		if(!p)return np->fa=m,last=np;
		sam* q=p->next[c];
		if(q->len==p->len+1)return np->fa=q,last=np;
		sam* nq=pq++;
		*nq=*q;
		nq->at=pl;
		q->fa=nq;
		np->fa=nq;
		nq->len=p->len+1;
		for(;p&&p->next[c]==q;p=p->fa)p->next[c]=nq;
		return last=np;
	}
	void link()
	{
		for(register sam* i=m+1;i<pp;++i)insert(i->fa,i);
		for(register sam* i=m+_n+1;i<pq;++i)insert(i->fa,i);
	}
};
Sam<500000> S;
Sam<1000000> T;
int dfn[1111111],dfc,bac[1111111];
void dfs(sam* o)
{
	dfn[o-S.m]=++dfc;
	for(register edge* p=o->fir;p;p=p->next)
		dfs(p->to);
	bac[o-S.m]=dfc;
}
char s[555555],mem[1111111],*pm=mem;
int max[2222222];
const int C=1048576;
void mdf(int p,int v)
{
	for(register int i=p+C;i;i>>=1)
		cmax(max[i],v);
}
int query(int l,int r)
{
	int ans=0;
	for(register int i=l-1+C,j=r+1+C;i+1!=j;i>>=1,j>>=1)
	{
		if(!(i&1))cmax(ans,max[i^1]);
		if(j&1)cmax(ans,max[j^1]);
	}
	return ans;
}
struct qu
{
	int l,r;
	char* t;
	int len;
	int no;
}q[111111]; 
bool operator <(const qu &x,const qu &y)
{
	return x.r<y.r;
}
int f[1111111];
long long A[111111];
int main()
{
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	scanf("%s",s+1);
	int n=strlen(s+1);
	for(register int i=1;i<=n;++i)S.ext(s[i]-'a',i);
	S.link();
	dfs(S.m);
	int m=io::F();
	for(register int i=1;i<=m;++i)
	{
		scanf("%s",pm+1);
		q[i]=(qu){io::F(),io::F(),pm,strlen(pm+1),i};
		pm+=q[i].len+1;
	}
	std::sort(q+1,q+m+1);
	int pq=1;
	for(register int i=1;i<=m;++i)
	{
		while(pq<=q[i].r)mdf(dfn[pq],pq),++pq;
		T.clear();
		for(register int j=1;j<=q[i].len;++j)
			T.ext(q[i].t[j]-'a',j);
		char* t=q[i].t;
		sam* now=S.m;
		int len=0;
		for(register int j=1;j<=q[i].len;++j)
		{
			while(1)
			{
				if(!now){len=0;now=S.m;break;}
				sam* to=now->next[t[j]-'a'];
				if(!to){now=now->fa;if(now)len=now->len;}
					else{now=to;++len;break;}
			}
			while(1)
			{
				int tmp=query(dfn[now-S.m],bac[now-S.m]);
				if(tmp&&tmp-len+1>=q[i].l)break;
				if(tmp&&tmp-now->fa->len+1>q[i].l){len=tmp-q[i].l+1;break;}
				now=now->fa;
				len=now->len;
			}
			f[j]=len;
		}
		long long ans=0;
		for(register sam* p=T.m+1;p<T.pq;++p)
		{
			if(p==T.pp)p=T.m+1000001;
			if(p==T.pq)break; 
			int at=p->at;
			int len=p->len;
			int flen=p->fa->len;
			if(f[at]<=flen)ans+=len-flen;
				else if(f[at]<len)ans+=len-f[at];
		}
		A[q[i].no]=ans;
	}
	for(register int i=1;i<=m;++i)
		printf("%lld\n",A[i]);
	return 0;
}

评测结果