代码

#include<algorithm>
#include<cstring>
#include<cctype>
#include<cstdio>
#define rep(i,x,y) for(int i=x; i<=y; ++i)
#define repd(i,x,y) for(int i=x; i>=y; --i)
#define mid (l+r>>1)

using namespace std;
const int N=500005;
typedef long long LL;
int n,m,q,seg_tot,T[N*45],ls[N*45],rs[N*45],cnt,h[N<<1];
char s[N],t[N];
int dfn[N<<1],pos[N<<1],siz[N<<1],ql,qr,root[N<<1],mx[N];
LL ans;
struct edge{int v,n;} e[N<<1];

void ins(int l,int r,int lst,int &rt,int x)
{
	if(!rt) rt=++seg_tot;
	if(l==r)
	{
		T[rt]=T[lst]+1;
		return;
	}
	if(x<=mid) ins(l,mid,ls[lst],ls[rt],x),rs[rt]=rs[lst];
	else ins(mid+1,r,rs[lst],rs[rt],x),ls[rt]=ls[lst];
	T[rt]=T[ls[rt]]+T[rs[rt]];
}

int query(int l,int r,int lst,int rt)
{
	if(!(T[rt]-T[lst])) return 0;
	if(l==r) return l;
	if(qr<=mid) return query(l,mid,ls[lst],ls[rt]);
	if(ql>mid) return query(mid+1,r,rs[lst],rs[rt]);
	int ret=query(mid+1,r,rs[lst],rs[rt]);
	if(!ret) return query(l,mid,ls[lst],ls[rt]);
	return ret;
}

void addedge(int u,int v)
{
	e[cnt]=(edge){v,h[u]},h[u]=cnt++;
}

struct Sam
{
	int fa[N<<1],len[N<<1],rk[N<<1],g[N<<1],bin[N<<1];
	int lst,tot,trf[N<<1][30];

	void init()
	{
		rep(i,1,tot)
		{
			bin[i]=fa[i]=len[i]=rk[i]=g[i]=0;
			rep(j,0,25) trf[i][j]=0;
		}
		lst=tot=1;
	}

	void ins(int c)
	{
		int u=lst,v,x=++tot;
		lst=tot,len[x]=len[u]+1;
		for(; u && !trf[u][c]; trf[u][c]=x,u=fa[u]);
		if(!u) fa[x]=1;
		else if(len[u]+1==len[v=trf[u][c]]) fa[x]=v;
		else
		{
			int w=++tot;
			len[w]=len[u]+1,fa[w]=fa[v];
			memcpy(trf[w],trf[v],sizeof(trf[v]));
			for(fa[x]=fa[v]=w; u && trf[u][c]==v; trf[u][c]=w,u=fa[u]);
		}
	}

	void dfs(int x)
	{
		dfn[x]=++*dfn,siz[x]=1;
		for(int i=h[x]; i!=-1; i=e[i].n)
			dfs(e[i].v),siz[x]+=siz[e[i].v];
	}	

	void build()
	{
		memset(h,-1,sizeof(h));
		rep(i,2,tot) addedge(fa[i],i);
		dfs(1);
		int p=1;
		rep(i,1,n) pos[dfn[p=trf[p][s[i]-'a']]]=i;
		rep(i,1,tot)
			if(pos[i]) ::ins(1,n,root[i-1],root[i],pos[i]);
			else root[i]=root[i-1];
	}

	bool check(int l,int x)
	{
		if(!x) return 1;
		int p=::query(1,n,root[dfn[x]-1],root[dfn[x]+siz[x]-1]);
		return !p || p-l+1<ql;
	}

	void get_mx()
	{
		int p=1,nw=0;
		rep(i,1,m)
		{
			while(p && check(nw+1,trf[p][t[i]-'a'])) p=fa[p],nw=len[p];
			if(!p) p=1,nw=0;
			else p=trf[p][t[i]-'a'],++nw;
			mx[i]=nw;
		}
	}

	void query()
	{
		int p=1;
		ans=0;
		rep(i,1,m) p=trf[p][t[i]-'a'],g[p]=mx[i];
		rep(i,1,tot) ++bin[len[i]];
		rep(i,1,n) bin[i]+=bin[i-1];
		rep(i,1,tot) rk[bin[len[i]]--]=i;
		repd(i,tot,1)
		{
			int x=rk[i];
			g[fa[x]]=max(g[fa[x]],g[x]);
			if(len[x]>g[x]) ans+=min(len[x]-g[x],len[x]-len[fa[x]]);
		}
		printf("%lld\n",ans);
	}
} t1,t2;

int getint()
{
	char ch;
	while(!isdigit(ch=getchar()));
	int x=ch-48;
	while(isdigit(ch=getchar())) x=x*10+ch-48;
	return x;
}

int main()
{
	scanf("%s",s+1),n=strlen(s+1);
	t1.init();
	rep(i,1,n) t1.ins(s[i]-'a');
	t1.build();
	q=getint();
	while(q--)
	{
		scanf("%s",t+1),ql=getint(),qr=getint();
		m=strlen(t+1);
		t2.init();
		rep(i,1,m) t2.ins(t[i]-'a');
		t1.get_mx();
		t2.query();
	}
	return 0;
}

评测结果