Aly_

​ SAM + 虚树 + 主席树。基本不需要动脑子但码量有点大。

​ 本方法不要求很熟悉 SAM 的相关内容。

​ 先建好 $S$ 的 SAM，然后分两步进行：

求出 $S$ 和 $T$ 的本质不同公共子串个数

​ 把 $T$ 放在 $S$ 的自动机上跑，维护 $nlen$ 表示当前最长匹配长度。

​ 如果能在字符边上前进就把 $nlen$ 加一，否则不断跳后缀链接并把 $nlen$ 缩小至对应节点的 $len$ 长度。

​ 把 $nlen$ 的信息记录在 $S$ 的自动机节点上。

​ 跑完一遍后，会得到对于每个 $S$ SAM 上节点 $i$，其在 $T$ 中的最长匹配长度 $f_i$。考虑一个节点的最长匹配长度的含义：该节点能代表的最长子串在 $T$ 中的最长匹配长度。于是，我们把 $f_i$ 对所有后缀链接到 $i$ 的节点 $j$ 的 $f_j$ 取 $\max$，若一个节点的 $f_i$ 大于其 $len$，我们把它对 $len$ 取 $\min$。于是一个节点和 $T$ 的本质不同子串数就是 $f_i-len_{link_i}$。加和即为 $\sum_i f_i-len_{link_i}$。

​ 首先容易想到一个暴力做法：直接对整棵 $link$ 树进行 DFS，更新所有点的 $f_i$ 后计算，这样单次最劣是 $O(|S|)$ 的。

​ 有一个更优秀的做法：注意到所有本质不同公共子串在 $link$ 树上的形态是一个过根联通块，我们取出所有 $i$ 满足 $f_i\ne len_i$，其均为该联通块上的叶子。换言之，求出这些点到根的路径并就可以得到本质不同公共子串数。

​ 路径并是经典的虚树问题。把所有点按 DFN 排序后每加上一个点的深度，就减去它与它前面的点的 LCA 的深度。复杂度单次最劣 $O(|T|\log |T|)$。运用欧拉序预处理技巧做到 $O(|T|)$。

求出 $S$ 的某一子串 $A=S_{l,r}$ 与 $T$ 的本质不同子串数

​ 把 $T$ 放在 $S$ 的自动机上跑。

​ 发现一个特性：$A$ 的 SAM 一定是 $S$ SAM 的子自动机。于是跑到一个点 $x$ 时，我们需要判断这点是否也在 $A$ 的自动机上。发现其实质是判断该点 $endpos_x$ 集合中是否有点落在区间 $[l+len_{link_x},r]$ 内。

​ SAM 上一个点的 $endpos$ 集合是所有 $link$ 指向它的点的 $endpos$ 之并。（如果它是一个前缀，再加上它本身的 $len$）

​ 这依然不好判断。我们在 $link$ 树下放之，发现该陈述又可以说是：

​ SAM 上一个点的 $endpos$ 集合是其在 $link$ 树子树内所有可以代表一个前缀的节点的 $len$。

​ 刚刚已经求出 DFN 序了，于是 $x$ 的子树变为一个连续区间 $[dfn_x,last_x]$。把前缀的 $len$ 数组映射到 DFN 序上记作数组 $\{L_i\}$，所问即为：

​ 问 $\{L_i\}$ 在 $[dfn_x,last_x]$ 区间中是否存在一个数，其值域在区间 $[l+len_{link_x},r]$ 内。如果有，求出值最大的那个数。

​ 注意到 $\{L_i\}$ 不随询问改变。主席树即可。复杂度 $O(|S|\log |S|)$。

​ 最后当然还要补集转化。

​ 总复杂度 $O(|S|\log |S|+\sum|T|\log |T|)$，可以通过。时空同级。（因此空间需要卡一下）

#include<bits/stdc++.h>
#define ll long long
#define N 2000000
#define mid (l+r)/2
using namespace std;
string st,q0;
int n,m,Q,q1,q2,na,col[N+1],ncol,nn;
int ch[2*N+1][26],lk[2*N+1],len[2*N+1],pb=1,lst=1,ans,rt,fl[N+1],aa;
int dpt[N+1],dfn[N+1],pdfn,bzb[21][N+1],logn[N+1],g[N+1],pg,ldfn[N+1];
bool seg[4*N+1];
int sit[21*N+1],son[21*N+1][2],fdfn[N+1],ep[N+1],pb1,me[N+1];
ll s[2*N+1];
vector<int>ve[N+1],ae;
void samadd(char c){
	len[++pb]=len[lst]+1;
	int np=lst;lst=pb,ep[lst]=len[lst];
	for(;np&&!ch[np][c-'a'];np=lk[np])ch[np][c-'a']=pb;
	if(!np)lk[pb]=max(rt,1);
	else{
		int nq=ch[np][c-'a'];
		if(len[nq]==len[np]+1)lk[pb]=nq;
		else{
			len[++pb]=len[np]+1,lk[pb]=lk[nq];
			lk[lst]=lk[nq]=pb;
			for(int i=0;i<26;i++)ch[pb][i]=ch[nq][i];
			for(;np&&ch[np][c-'a']==nq;np=lk[np])ch[np][c-'a']=pb;
		}
	}
}
void segadd(int u,int l,int r,int np,int nx){
	if(l!=r){
		if(np<=mid)segadd(u*2,l,mid,np,nx);
		else segadd(u*2+1,mid+1,r,np,nx);
		seg[u]=(seg[u*2]|seg[u*2+1]);
	}else seg[u]=nx;
}
bool segreq(int u,int l,int r,int nl,int nr){
	if(l>nr||r<nl||nl>nr)return 0;
	else if(l>=nl&&r<=nr)return seg[u];
	else return segreq(u*2,l,mid,nl,nr)|segreq(u*2+1,mid+1,r,nl,nr);
}
void dfs0(int x){
	dfn[x]=ldfn[x]=++pdfn,fdfn[pdfn]=x,dpt[x]=dpt[lk[x]]+1;
	for(int i=0;i<ve[x].size();i++)dfs0(ve[x][i]),ldfn[x]=max(ldfn[x],ldfn[ve[x][i]]);
}
void ycl(){
	dfs0(1);
	for(int i=2;i<=pb;i++)logn[i]=logn[i/2]+1,bzb[0][i]=lk[i];bzb[0][1]=1;
	for(int i=1;i<=logn[pb];i++)for(int j=1;j<=pb;j++)bzb[i][j]=bzb[i-1][bzb[i-1][j]];
}
int lca(int x,int y){
	if(dpt[x]<dpt[y])swap(x,y);
	for(;dpt[x]>dpt[y];x=bzb[logn[dpt[x]-dpt[y]]][x]);
	if(x==y)return x;
	for(int i=logn[n];i>=0;i--)if(bzb[i][x]!=bzb[i][y])x=bzb[i][x],y=bzb[i][y];
	return lk[x];
}
void samclr(int l,int r){
	for(int i=l;i<=r;i++)memset(ch[i],0,sizeof(ch[i])),len[i]=lk[i]=fl[i]=s[i]=0,ve[i].clear();
}
void sitadd(int u,int nu,int l,int r,int np){
	if(l==r)sit[u]=l;
	else{
		if(np<=mid){
			son[u][0]=++pb1,son[u][1]=son[nu][1];
			sitadd(son[u][0],son[nu][0],l,mid,np);
		}else{
			son[u][1]=++pb1,son[u][0]=son[nu][0];
			sitadd(son[u][1],son[nu][1],mid+1,r,np);
		}sit[u]=sit[son[u][0]]+sit[son[u][1]];
	}
}
bool sitreq0(int ul,int ur,int l,int r,int nr){
	if(l==r||nr>=r)return sit[ur]-sit[ul];
	else if(nr>mid){
		if(sit[son[ur][0]]-sit[son[ul][0]])return 1;
		else return sitreq0(son[ul][1],son[ur][1],mid+1,r,nr);
	}else return sitreq0(son[ul][0],son[ur][0],l,mid,nr);
}
int sitreq(int ul,int ur,int l,int r,int np){
	if(l==r){
		if(sit[ur]-sit[ul]==0)return 0;
		else return l;
	}else{
		if(np<=mid)return sitreq(son[ul][0],son[ur][0],l,mid,np);
		else{
			if(sitreq0(son[ul][1],son[ur][1],mid+1,r,np))return sitreq(son[ul][1],son[ur][1],mid+1,r,np);
			else return sitreq(son[ul][0],son[ur][0],l,mid,np);
		}
	}
}
bool comp(int x,int y){return dfn[x]<dfn[y];}
int hf(int x,int nl,int nr){
	if(!x)return 0;
	if(nl==1&&nr==n)return 999999;
	if(col[x]==ncol)return me[x];
	col[x]=ncol;
	int np=sitreq(dfn[x]-1,ldfn[x],1,n,nr);
	if(np<nl+len[lk[x]])return me[x]=0;
	else return me[x]=np-nl+1;
}
ll sutree(){
	ll nans=0;
	sort(g+1,g+pg+1,comp);
	nans+=min(fl[g[1]],hf(g[1],q1,q2));
	for(int i=2;i<=pg;i++){
		nans-=len[lca(g[i],g[i-1])],nans+=min(fl[g[i]],hf(g[i],q1,q2));
	}
	return nans;
}
ll mdfs(int x){
	if(s[x])return s[x];
	s[x]=1;
	for(int i=0;i<26;i++)if(ch[x][i])s[x]+=mdfs(ch[x][i]);
	return s[x];
}
void plt(int x,int nlen){
	if(!fl[x]){
		ae.push_back(x);
		segadd(1,1,nn,dfn[x],1);
	}
	fl[x]=max(fl[x],nlen);
}
void sitbuild(){
	pb1=nn;
	for(int i=1;i<=nn;i++){
		if(ep[fdfn[i]])sitadd(i,i-1,1,n,ep[fdfn[i]]);
		else son[i][0]=son[i-1][0],son[i][1]=son[i-1][1],sit[i]=sit[i-1];
	}
}
signed main(){
	cin>>st;
	n=st.size();
	for(int i=1;i<=n;i++)samadd(st[i-1]);nn=pb;
	for(int i=1;i<=pb;i++)if(lk[i])ve[lk[i]].push_back(i);
	ycl(),sitbuild();
	cin>>Q;
	while(Q--){
		ncol=Q+1;
		pdfn=0;
		aa=0;
		cin>>q0>>q1>>q2;
		m=q0.size();
		pb=lst=rt=nn+1;
		int np=1,nlen=0;fl[np]=0;
		for(int i=0;i<m;i++){
			if(hf(ch[np][q0[i]-'a'],q1,q2)){
				np=ch[np][q0[i]-'a'],nlen++;
				plt(np,nlen);
			}else{
				while(np!=1&&!hf(ch[np][q0[i]-'a'],q1,q2))np=lk[np],nlen=min(nlen,len[np]),plt(np,nlen);
				if(hf(ch[np][q0[i]-'a'],q1,q2))np=ch[np][q0[i]-'a'],nlen++,plt(np,nlen);
			}
		}
		pg=0;
		for(int i=0;i<ae.size();i++)if(!segreq(1,1,nn,dfn[ae[i]]+1,ldfn[ae[i]]))g[++pg]=ae[i];
		ll nans=sutree();
		for(int i=0;i<m;i++)samadd(q0[i]);
		nans=mdfs(rt)-nans-1;
		samclr(rt,pb);
		cout<<nans<<endl;
		for(int i=0;i<ae.size();i++)fl[ae[i]]=0,segadd(1,1,nn,dfn[ae[i]],0);
		ae.clear();
	}
	return 0;
}