重新做一遍，感觉脑子清楚多了
思维过程
首先我们不考虑区间限制咋做（很常见套路，先不考虑区间限制），换句话说我们要面对整个串 (S)。
一个常见思考方式：数本质不同串数，对于SAM上每个节点单独考虑
那我们把 (T) 的 SAM 搞出来，考虑每个节点。首先有一个显然的性质，如果一个串满足条件，那么它加点字符还是满足的 ；如果不满足条件，那么它的子串还是不满足的。
这个被称作 “包含关系”，对于一个字符串题，这是一个很值得考虑，很重要的性质。
对于满足这样性质的条件，我们一般可以考虑用最长/最短满足条件的长度之类的方法处理。
SAM一个节点表示的串有一个特征，它一定是最长的串不断的删首字符得到，并且在串中出现位置的集合相同。那么一个节点中的串是否“满足条件”，一定是两段的：长的若干个串都满足，到某个串开始，都不满足。
那我们怎么知道哪个串开始就不满足了呢？对于某个节点，我们任意取一个 (endpos) 集合中的位置 (p)，然后找到 (T) 以 (p) 结尾的子串中最长的串使得它是 (S) 的子串，设这个串长为 (l)。可以想象出来，这个 (l) 是“最长不合法长度”，再 (+1) 就是 "最短合法长度“。然后这样就可以去除掉一个节点中不合法的那些了。
那我们怎么得到这个最长的长度 (l) 呢？仔细一想，发现这个锤子玩意就是匹配长度，用和AC自动机类似的跳fail的方法就行了。
至此，我们解决了不考虑区间的case
现在我们考虑加入了区间限制咋做。我们显然不能把这个区间的 SAM 单独建出来，但是我们可以考虑在整个 (S) 的 SAM 上瞎跳跳，得到一个在区间中的匹配。
由于我们需要涉及到区间，即具体位置，一下想到要线段树合并。线段树合并完了，其实问题就没了，我们每次跳fail找匹配的时候，看看它是否出现在区间中，并且左边有足够的空位 （如果串长为 (len)，那 (endpos) 就得在 ([l+len-1,r]) 中有东西），就行了。
说起来简单，线段树合并可写死人
总结
几个思维方式
- 先不看区间限制，再考虑如何加上
- 在SAM上按节点考虑
- 对于字符串题，尤其涉及子串不子串的，可以考虑 “包含性质”
代码
#include <bits/stdc++.h>
using namespace std;
bool alpha;
namespace Flandre_Scarlet
{
#define N 2000006
#define V 2000000
#define F(i,l,r) for(int i=l;i<=r;++i)
#define D(i,r,l) for(int i=r;i>=l;--i)
#define Fs(i,l,r,c) for(int i=l;i<=r;c)
#define Ds(i,r,l,c) for(int i=r;i>=l;c)
#define MEM(x,a) memset(x,a,sizeof(x))
#define FK(x) MEM(x,0)
#define Tra(i,u) for(int i=G.st(u),v=G.to(i);~i;i=G.nx(i),v=G.to(i))
#define p_b push_back
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define iter(a,p) (a.begin()+p)
int I() {char c=getchar(); int x=0; int f=1; while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar(); while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return ((f==1)?x:-x);}
template <typename T> void Rd(T& arg){arg=I();}
template <typename T,typename...Types> void Rd(T& arg,Types&...args){arg=I(); Rd(args...);}
void RA(int *p,int n) {F(i,1,n) *p=I(),++p;}
char s[N]; int n;
int q,m; char t[N];
void Input()
{
scanf("%s",s+1); n=strlen(s+1);
q=I();
}
int sl,sr;
// 一般SAM线段树合并系列
class MSegmentTree // 线段树合并, 支持插入, 合并, 询问区间中有没有数(即非空节点)
{
public:
#define M 33000007
#define lson lp[ix],L,mid
#define rson rp[ix],mid+1,R
int lp[M],rp[M],rt[N],tot=0;
void ins(int pos,int &ix,int L=1,int R=V)
{
if (!ix) ix=++tot;
if (L==R) return;
int mid=(L+R)>>1;
if (pos<=mid) ins(pos,lson);
else ins(pos,rson);
}
int merge(int ii,int ix,int L=1,int R=V)
{
if (!ii or !ix) return ii|ix;
int o=++tot;
if (L!=R)
{
int mid=(L+R)>>1;
lp[o]=merge(lp[ii],lson);
rp[o]=merge(rp[ii],rson);
}
return o;
}
bool have(int l,int r,int &ix,int L=1,int R=V)
{
if (l>R or L>r or l>r or !ix) return 0;
if (l<=L and R<=r) return 1;
int mid=(L+R)>>1;
return have(l,r,lson)|have(l,r,rson);
}
}T;
class Suffix_Automaton // 一般通过SAM, 一个是S的SAM, 一个是T的SAM
{
public:
int tot=1,las=1;
int nx[N][26],len[N],lk[N];
int fir[N]; // endpos中最左边那个, 由于只需要任意一个, 所以搞一个好搞的
void clear(int nn) {F(i,0,2*nn) len[i]=lk[i]=fir[i]=0,MEM(nx[i],0); tot=las=1;}
void extend(int c,int id,bool f=0)
{
// f: 是否要搞线段树合并
// S需要, T不需要
int cur=++tot;
len[cur]=len[las]+1;
fir[cur]=id;
if (f)
{
T.ins(id,T.rt[cur]);
}
int p=las;
while(p and !nx[p][c])
{
nx[p][c]=cur; p=lk[p];
}
if (!p)
{
lk[cur]=1;
}
else
{
int q=nx[p][c];
if (len[q]==len[p]+1)
{
lk[cur]=q;
}
else
{
int q2=++tot;
len[q2]=len[p]+1;
fir[q2]=fir[q]; lk[q2]=lk[q]; F(i,0,25) nx[q2][i]=nx[q][i];
lk[q]=lk[cur]=q2;
while(p and nx[p][c]==q)
{
nx[p][c]=q2; p=lk[p];
}
}
}
las=cur;
}
int cc[N],id[N];
void sakuya()
{
F(i,1,tot) cc[len[i]]++;
F(i,1,tot) cc[i]+=cc[i-1];
D(i,tot,1) id[cc[len[i]]--]=i;
D(i,tot,2)
{
int x=id[i];
T.rt[lk[x]]=T.merge(T.rt[lk[x]],T.rt[x]);
}
}
}S,St;
int p[N]; // 对于T的每个位置, 维护在S中的最长匹配长度 (最长不合法长度)
void Sakuya()
{
F(i,1,n) S.extend(s[i]-'a',i,1);
S.sakuya();
while(q-->0)
{
scanf("%s",t+1); m=strlen(t+1);
Rd(sl,sr);
int cur=1;
F(i,1,m) p[i]=0;
F(i,1,m)
{
p[i]=p[i-1]; int &len=p[i];
int c=t[i]-'a';
while(1)
{
int nexp=S.nx[cur][c];
if (nexp and T.have(sl+len,sr,T.rt[nexp]))
// 有这个转移, 并且还在 [sl,sr] 间
{
++len; cur=nexp; break;
}
if (!len) break;
--len;
if (len==S.len[S.lk[cur]]) cur=S.lk[cur];
// 注意这里不能直接跳cur
// 为什么?
}
}
F(i,1,m) St.extend(t[i]-'a',i);
long long ans=0;
F(i,2,St.tot)
{
int x=St.fir[i],mx=St.len[i],mn=St.len[St.lk[i]];
int no=p[x];
ans+=max(mx-max(mn,no),0);
// 稍微讨论一下
}
printf("%lld
",ans);
St.clear(m+1);
}
}
void IsMyWife()
{
Input();
Sakuya();
}
}
#undef int //long long
bool beta;
int main()
{
Flandre_Scarlet::IsMyWife();
getchar();
return 0;
}
/*
关于为啥不能直接跳cur:
见 https://www.luogu.com.cn/discuss/show/323751
*/