代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1000005,M=2000005,K=26,E=20000005;
int n,m,q,ql,qr;
char s[N],t[N];
int lim[N];
namespace sams
{
	int ind,la,tot;
	int dir[N][K],len[N],fail[N],fro[N],fr[N],nxt[N],em[N],lc[E],rc[E],now[E],sye[E],poe[N];
	inline void addedge(int u,int v)
	{
		static int tot=0;
		++tot;
		nxt[tot]=fr[u];
		fr[u]=tot;
		em[tot]=v;
	}
	#define mid ((l+r)>>1)
	void ins(int &p,int l,int r,int q,int x)
	{
		if(p==0)
		{
			p=++tot;
			lc[p]=rc[p]=now[p]=0;
			sye[p]=x;
		}
		if(l==r)
		{
			now[p]++;
			return;
		}
		if(q<=mid)
			ins(lc[p],l,mid,q,x);
		else
			ins(rc[p],mid+1,r,q,x);
		now[p]=now[lc[p]]+now[rc[p]];
	}
	int query(int p,int l,int r,int ql,int qr)
	{
		if(p==0)
			return 0;
		if(ql<=l&&r<=qr)
			return now[p];
		int ans=0;
		if(l<=qr&&ql<=mid)
			ans+=query(lc[p],l,mid,ql,qr);
		if(mid+1<=qr&&ql<=r)
			ans+=query(rc[p],mid+1,r,ql,qr);
		return ans;
	}
	inline int merge(int p,int q,int l,int r,int x)
	{
		if(p==0)
			return q;
		if(q==0)
			return p;
		if(sye[p]==x)
			now[p]+=now[q];
		else
		{
			++tot;
			lc[tot]=lc[p];
			rc[tot]=rc[p];
			now[tot]=now[p];
			sye[tot]=x;
			p=tot;
			now[p]+=now[q];
		}
		if(l==r)
			return p;
		lc[p]=merge(lc[p],lc[q],l,mid,x);
		rc[p]=merge(rc[p],rc[q],mid+1,r,x);
		now[p]=now[lc[p]]+now[rc[p]];
		return p;
	}
	#undef mid
	void ins(int c,int le)
	{
		++ind;
		ins(fro[ind],1,n,le,ind);
		poe[ind]=le;
		len[ind]=len[la]+1;
		while(la!=0&&dir[la][c]==0)
		{
			dir[la][c]=ind;
			la=fail[la];
		}
		if(la==0&&dir[la][c]==0)
		{
			dir[la][c]=ind;
			fail[ind]=la;
			la=ind;
			return;
		}
		else if(len[dir[la][c]]==len[la]+1)
		{
			fail[ind]=dir[la][c];
			la=ind;
			return;
		}
		else
		{
			int p=dir[la][c];
			++ind;
			len[ind]=len[la]+1;
			fail[ind]=fail[p];
			poe[ind]=poe[p];
			ins(fro[ind],1,n,poe[ind],ind);
			memmove(dir[ind],dir[p],sizeof(dir[ind]));
			fail[p]=ind;
			fail[ind-1]=ind;
			for(int j=la;dir[j][c]==p;j=fail[j])
				dir[j][c]=ind;
			la=ind-1;
			return;
		}
	}
	void build(int d)
	{
		for(int j=fr[d];j!=0;j=nxt[j])
		{
			build(em[j]);
			fro[d]=merge(fro[d],fro[em[j]],1,n,d);
		}
	}
};
namespace samt
{
	int ind,la;
	int dir[M][K],len[M],fail[M],pos[M];
	inline void clear()
	{
		ind=la=0;
		memset(dir[0],0,sizeof(dir[0]));
	}
	void ins(int c,int le)
	{
		++ind;
		memset(dir[ind],0,sizeof(dir[ind]));
		pos[ind]=le;
		len[ind]=len[la]+1;
		while(la!=0&&dir[la][c]==0)
		{
			dir[la][c]=ind;
			la=fail[la];
		}
		if(la==0&&dir[la][c]==0)
		{
			dir[la][c]=ind;
			fail[ind]=la;
			la=ind;
			return;
		}
		else if(len[dir[la][c]]==len[la]+1)
		{
			fail[ind]=dir[la][c];
			la=ind;
			return;
		}
		else
		{
			int p=dir[la][c];
			++ind;
			len[ind]=len[la]+1;
			fail[ind]=fail[p];
			pos[ind]=pos[p];
			memmove(dir[ind],dir[p],sizeof(dir[ind]));
			fail[p]=ind;
			fail[ind-1]=ind;
			for(int j=la;dir[j][c]==p;j=fail[j])
				dir[j][c]=ind;
			la=ind-1;
			return;
		}
	}
};
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++)
		sams::ins(s[i]-'a',i);
	for(int i=1;i<=sams::ind;i++)
		sams::addedge(sams::fail[i],i);
	sams::build(0);
	scanf("%d",&q);
	while(q--)
	{
		scanf("%s",t+1);
		m=strlen(t+1);
		scanf("%d%d",&ql,&qr);
		samt::clear();
		for(int i=1;i<=m;i++)
			samt::ins(t[i]-'a',i);
		for(int i=1,now=0,le=0;i<=m;i++)
		{
			while(1)
			{
				if(sams::dir[now][t[i]-'a']!=0&&sams::query(sams::fro[sams::dir[now][t[i]-'a']],1,n,ql+le,qr)>0)
				{
					now=sams::dir[now][t[i]-'a'];
					le++;
					break;
				}
				if(le==0)
					break;
				le--;
				if(le==sams::len[sams::fail[now]])
					now=sams::fail[now];
			}
			lim[i]=le;
		}
		ll ans=0;
		for(int i=1;i<=samt::ind;i++)
			ans+=max(0,samt::len[i]-max(samt::len[samt::fail[i]],lim[samt::pos[i]]));
		printf("%lld\n",ans);
	}
	return 0;
}

评测结果