考虑(l=1,r=|S|)的情况：
对(S)串建SAM，(T)在上面匹配，可以得到每个位置(i)的后缀的最长匹配长度(mx[i])。
因为要去重，对(T)也建SAM，计算上面所有节点的答案。记(pos[i])表示(i)节点第一次出现的下标（同一节点代表的串出现的位置集合相同，所以随便记一个即可）。
则节点(i)的答案为：(max(0, len[i]-max(len[fa[i]], mx[pos[i]])))。
考虑(l,r)任意的情况：
要判断(T)能否在(S[l,r])上匹配，也就是匹配的时候只能走在(S[l,r])出现过的节点。
线段树合并，自底向上合并right集合，就可以得到SAM上每个节点出现过的位置（right）。
如果已匹配长度为(now)，那么区间查的时候要查([l+now,r])啊（跳(fa)时要同时改(now)）（要不还是68分）。
而且(now)应该是每次减一，而不是令(p)直接跳(fa)（但还是有96分）。
好像只要还记得SAM的套路就没那么难？（反正我已经忘了）
明年还出SAM就好了。
/*
LOJ:10770ms 337788K
洛谷:16362ms 348.41MB
BZOJ:408052kb 28352ms
*/
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=1e6+5;
int mx[N],root[N];
char s[N];
struct Segment_Tree
{
#define ls son[x][0]
#define rs son[x][1]
#define lson ls,l,m
#define rson rs,m+1,r
#define S N*20
int tot,son[S][2];
#undef S
void Insert(int &x,int l,int r,int p)
{
/*if(!x)*/ x=++tot;//
if(l==r) return;
int m=l+r>>1;
p<=m ? Insert(lson,p) : Insert(rson,p);
}
int Merge(int x,int y)
{
if(!x||!y) return x|y;
int now=++tot;
son[now][0]=Merge(ls,son[y][0]), son[now][1]=Merge(rs,son[y][1]);
return now;
}
bool Query(int x,int l,int r,int L,int R)
{
if(!x) return 0;
if(L<=l && r<=R) return 1;
int m=l+r>>1;
if(L<=m)
if(m<R) return Query(lson,L,R)||Query(rson,L,R);
else return Query(lson,L,R);
return Query(rson,L,R);
}
#undef ls
#undef rs
}Tr;
struct Suffix_Automaton
{
int n,tot,las,fa[N],son[N][26],len[N],tm[N],A[N],pos[N];
void Insert(int c,int id)
{
int np=++tot,p=las;
len[las=np]=len[p]+1, pos[np]=id;
for(;p&&!son[p][c]; p=fa[p]) son[p][c]=np;
if(!p) fa[np]=1;
else
{
int q=son[p][c];
if(len[q]==len[p]+1) fa[np]=q;
else
{
int nq=++tot;
len[nq]=len[p]+1, pos[nq]=pos[q];
memcpy(son[nq],son[q],sizeof son[q]);
fa[nq]=fa[q], fa[q]=fa[np]=nq;
for(; son[p][c]==q; p=fa[p]) son[p][c]=nq;
}
}
}
void Build_S(char *s,int l)
{
memset(son,0,(tot+2)*sizeof son[0]);
tot=las=1, n=l;
for(int i=1; i<=n; ++i) Insert(s[i]-'a',i),Tr.Insert(root[las],1,n,i);
for(int i=1; i<=tot; ++i) ++tm[len[i]];
for(int i=1; i<=n; ++i) tm[i]+=tm[i-1];
for(int i=1; i<=tot; ++i) A[tm[len[i]]--]=i;
for(int i=tot,x=A[i]; i>1; x=A[--i]) root[fa[x]]=Tr.Merge(root[x],root[fa[x]]);
}
void Build_T(char *s,int l)
{
memset(son,0,(tot+2)*sizeof son[0]);
tot=las=1, n=l;
for(int i=1; i<=l; ++i) Insert(s[i]-'a',i);
}
}S,T;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
void Solve(int ls)
{
scanf("%s",s+1);
int l=read(),r=read(),n=strlen(s+1);
T.Build_T(s,n);
for(int i=1,now=0,p=1,c; i<=n; mx[i++]=now)
{
c=s[i]-'a';
while(1)
{
if(!Tr.Query(root[S.son[p][c]],1,ls,l+now,r))
{
if(!now) break;//匹配长度为0了要再匹配一次
--now;
if(now==S.len[S.fa[p]]) p=S.fa[p];
}
else {++now, p=S.son[p][c]; break;}
}
// if(Tr.Query(root[S.son[p][c]],1,ls,l+now,r)) p=S.son[p][c], ++now;
// else
// {
// for(; p&&!Tr.Query(root[S.son[p][c]],1,ls,l+now,r); p=S.fa[p],now=S.len[p]);
// if(!p) p=1, now=0;
// else now=S.len[p]+1, p=S.son[p][c];//这样写96分 还只错了一个询问
// }
}
LL ans=0;
for(int i=2; i<=T.tot; ++i)
ans+=std::max(0,T.len[i]-std::max(T.len[T.fa[i]],mx[T.pos[i]]));
printf("%lld
",ans);
}
int main()
{
// freopen("name.in","r",stdin);
// freopen("name.out","w",stdout);
scanf("%s",s+1); int ls=strlen(s+1);
S.Build_S(s,ls);
for(int Q=read(); Q--; Solve(ls));
return 0;
}
68分代码：
/*
对S串建SAM，T在上面匹配，可以得到每个位置i的后缀的最长匹配长度mx[i]。
因为要去重，对T也建SAM，计算上面所有节点的答案。记pos[i]表示i节点第一次出现的下标（同一节点代表的串出现的位置集合相同）。
则节点i的答案为：max(0, len[i]-max(len[fa[i]], mx[pos[i]]))。
*/
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=1e6+5;
int mx[N];
char s[N];
struct Suffix_Automaton
{
int n,tot,las,fa[N],son[N][26],len[N],pos[N];
void Insert(int c,int id)
{
int np=++tot,p=las;
len[las=np]=len[p]+1, pos[np]=id;
for(;p&&!son[p][c]; p=fa[p]) son[p][c]=np;
if(!p) fa[np]=1;
else
{
int q=son[p][c];
if(len[q]==len[p]+1) fa[np]=q;
else
{
int nq=++tot;
len[nq]=len[p]+1, pos[nq]=pos[q];
memcpy(son[nq],son[q],sizeof son[q]);
fa[nq]=fa[q], fa[q]=fa[np]=nq;
for(; son[p][c]==q; p=fa[p]) son[p][c]=nq;
}
}
}
void Build(char *s,int l)
{
memset(son,0,(tot+2)*sizeof son[0]);
tot=las=1, n=l;
for(int i=1; i<=n; ++i) Insert(s[i]-'a',i);
}
}S,T;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
void Solve()
{
int n=strlen(s+1);
for(int i=1,now=0,p=1,c; i<=n; mx[i++]=now)
{
if(S.son[p][c=s[i]-'a']) p=S.son[p][c], ++now;
else
{
for(; p&&!S.son[p][c]; p=S.fa[p]);
if(!p) p=1, now=0;
else now=S.len[p]+1, p=S.son[p][c];
}
}
LL ans=0;
for(int i=2; i<=T.tot; ++i)
ans+=std::max(0,T.len[i]-std::max(T.len[T.fa[i]],mx[T.pos[i]]));
printf("%lld
",ans);
}
int main()
{
freopen("name.in","r",stdin);
freopen("name.out","w",stdout);
scanf("%s",s+1);
S.Build(s,strlen(s+1)); int Q=read();
for(int i=1; i<=Q; ++i)
{
scanf("%s",s+1);
int l=read(),r=read();
T.Build(s,strlen(s+1)), Solve();
}
return 0;
}