代码

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
#define _(d) while(d((ch=getchar()-48)>=0))
inline int get(){
	char ch;_(!);int x=ch;
	_() x=(x<<3)+(x<<1)+ch;
	return x;
}
const int N=500005<<1;
int n,m,tot,et,rt[N],h[N],to[N],nx[N],in[N],ou[N],a[N],mt[N],ps[N];
char sr[N];
class segtree{
	struct node{
		int v;
		node *lc,*rc;
	}po[N*20],*tt=po,*root[N];
	int qt,num;
	void build(node *&o,int l,int r){
		o=++tt;
		if(l==r) return;
		int mid=l+r>>1;
		build(o->lc,l,mid);
		build(o->rc,mid+1,r);
	}
	void insert(node *&o,int l,int r,int k){
		*(++tt)=*o,++((o=tt)->v);
		if(l==r) return;
		int mid=l+r>>1;
		if(k<=mid) insert(o->lc,l,mid,k);
		else insert(o->rc,mid+1,r,k);
	}
	int ask(node *s,node *t,int l,int r){
		if(r<=qt) return t->v-s->v;
		if(l>qt) return 0;
		int mid=l+r>>1;
		return ask(s->lc,t->lc,l,mid)+ask(s->rc,t->rc,mid+1,r);
	}
	int qry(node *s,node *t,int l,int r){
		if(l==r) return l;
		int mid=l+r>>1,va=t->lc->v-s->lc->v;
		if(va<num){
			num-=va;
			return qry(s->rc,t->rc,mid+1,r);
		}return qry(s->lc,t->lc,l,mid);
	}
	public:
	void build(){
		build(root[0],1,n);
		for(int i=1;i<=tot;++i){
			root[i]=root[i-1];
			if(a[i]) insert(root[i],1,n,a[i]);
		}
	}
	int qry(int o,int t){
		qt=t,num=ask(root[in[o]-1],root[ou[o]],1,n);
		if(!num) return 0;
		return qry(root[in[o]-1],root[ou[o]],1,n);
	}
}tr;
class sam{
	struct node{
		int mx;
		node *pr,*ch[26];
		node(int x=0){
			pr=0,mx=x;
			memset(ch,0,sizeof(ch));
		}
	}po[N],*tt,*root,*last;
	void add(int u,int v){
		to[++et]=v,nx[et]=h[u],h[u]=et;
	}
	void dfs(int p){
		in[p]=++tot;
		a[tot]=ps[p];
		for(int i=h[p];i;i=nx[i])
			dfs(to[i]);
		ou[p]=tot;
	}
	public:
	void init(){
		root=last=tt=po;*root=node();
	}
	void extend(int k){
		node *p=last,*np=++tt;
		*np=node(ps[np-po]=rt[np-po]=p->mx+1);
		for(;p&&!p->ch[k];p->ch[k]=np,p=p->pr);
		if(!p) np->pr=root;
		else{
			node *q=p->ch[k];
			if(p->mx+1==q->mx) np->pr=q;
			else{
				node *nq=++tt;
				*nq=node(p->mx+1);rt[nq-po]=rt[q-po];
				memcpy(nq->ch,q->ch,sizeof(q->ch));
				nq->pr=q->pr,q->pr=np->pr=nq;
				for(;p&&p->ch[k]==q;p->ch[k]=nq,p=p->pr);
			}
		}last=np;
	}
	void proc(){
		for(node *i=po;i<=tt;++i) h[i-po]=0;
		for(node *i=po+1;i<=tt;++i)
			add(i->pr-po,i-po);
		dfs(0);
	}
	void solve(int qs,int qt){
		node *o=root;int l=0;
		for(int i=1;i<=m;++i){
			bool fl=0;
			while(o&&!o->ch[sr[i]]) o=o->pr,fl=1;
			if(o){
				if(fl) l=o->mx;
				++l,o=o->ch[sr[i]];
				while(l){
					if(tr.qry(o-po,qt)-qs+1<l){
						if((--l)==o->pr->mx) o=o->pr;
					}else break;
				}
				mt[i]=l;
			}else o=root,l=mt[i]=0;
		}
	}
	long long qry(){
		long long ret=0;
		for(node* i=po+1;i<=tt;++i)
			ret+=max(0,i->mx-max(i->pr->mx,mt[rt[i-po]]));
		return ret;
	}
}S,T;
int main(){
	S.init();char ch;
	while(isalpha(ch=getchar()))
		++n,S.extend(ch-'a');
	S.proc();
	tr.build();
	for(int Q=get(),qs,qt;Q--;){
		T.init(),m=0;
		while(isalpha(ch=getchar()))
			T.extend(sr[++m]=ch-'a');
		qs=get(),qt=get();
		S.solve(qs,qt);
		printf("%lld\n",T.qry());
	}
	return 0;
}

评测结果