题目分析

先考虑 68 分做法。

给 S 和 T 都建一个 SAM，T 的 SAM 所有节点代表子串的并集就是 T 中本质不同的子串个数，我们顺便再乱记一个 T 每个节点的 endpos 集合里的元素。将 T 放到 S 的 SAM 上去跑一遍，就可以知道每一个 endpos 与 S 的最长匹配，然后可以知道 T 的 SAM 上一个节点能贡献多少名字了。

考虑 100 分，现在唯一的问题是，我把 T 放到 S 上去跑的时候，可能匹配到的子串不在区间内，这就很尴尬。

我们搞出 S 的 SAM 的 parent 树，然后弄出每个节点的 dfs 序，再用一个主席树，对每个 dfs 序位置建立一棵线段树，线段树维护每一个 endpos 是否出现过。现在假设在 T 到 S 的 SAM 上跑匹配的时候，匹配长度假设是 d，那么要走的下一个节点，必须满足 endpos 集合里存在一个元素，满足 $l \leq x+d \leq r$且 $l \leq x \leq r$，反正也就是 $l-d \leq x \leq r$
当然如果发现走不了，要做的第一件事不是立刻条 pre 换匹配，而是减少一下 $d$的值，再检验。

本题卡空间，所以 litble 非常无奈地写了两遍 SAM

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int N=1000005;
typedef long long LL;
char S[N],T[N<<1];
int n,m,tot,Q,tim;LL ans;
struct SAM{
    int ch[N<<1][26],step[N<<1],pre[N<<1],id[N<<1],SZ,last;
    bool orz[N<<1];
    void ins(int x,int QAQ) {
        int np=++SZ,p=last;
        orz[np]=1,id[np]=QAQ,last=np,step[np]=step[p]+1;
        while(p&&!ch[p][x]) ch[p][x]=np,p=pre[p];
        if(!p) pre[np]=1;
        else {
            int q=ch[p][x];
            if(step[q]==step[p]+1) pre[np]=q;
            else {
                int nq=++SZ;step[nq]=step[p]+1,id[nq]=id[q];
                for(RI i=0;i<26;++i) ch[nq][i]=ch[q][i];
                pre[nq]=pre[q],pre[q]=pre[np]=nq;
                while(ch[p][x]==q) ch[p][x]=nq,p=pre[p];
            }
        }
    }
}T1;
struct MLEQAQ{
    int ch[N<<2][26],step[N<<2],pre[N<<2],id[N<<2],SZ,last;
    void ins(int x,int QAQ) {
        int np=++SZ,p=last;
        id[np]=QAQ,last=np,step[np]=step[p]+1;
        while(p&&!ch[p][x]) ch[p][x]=np,p=pre[p];
        if(!p) pre[np]=1;
        else {
            int q=ch[p][x];
            if(step[q]==step[p]+1) pre[np]=q;
            else {
                int nq=++SZ;step[nq]=step[p]+1,id[nq]=id[q];
                for(RI i=0;i<26;++i) ch[nq][i]=ch[q][i];
                pre[nq]=pre[q],pre[q]=pre[np]=nq;
                while(ch[p][x]==q) ch[p][x]=nq,p=pre[p];
            }
        }
    }
}T2;

int rt[N<<1],SZ;
struct node{int ls,rs,v;}tr[N*20];
void chan(int &x,int y,int l,int r,int wz) {
    x=++SZ,tr[x]=tr[y],++tr[x].v;
    int mid=(l+r)>>1;
    if(l==r) return;
    if(wz<=mid) chan(tr[x].ls,tr[y].ls,l,mid,wz);
    else chan(tr[x].rs,tr[y].rs,mid+1,r,wz);
}
int query(int x,int y,int l,int r,int s,int t) {
    if(l<=s&&t<=r) return tr[y].v-tr[x].v;
    int mid=(s+t)>>1,re=0;
    if(l<=mid) re=query(tr[x].ls,tr[y].ls,l,r,s,mid);
    if(mid+1<=r) re+=query(tr[x].rs,tr[y].rs,l,r,mid+1,t);
    return re;
}

int h[N],ne[N],to[N],in[N],out[N],repos[N],lim[N];
void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
void dfs(int x) {
    in[x]=++tim,repos[tim]=x;
    for(RI i=h[x];i;i=ne[i]) dfs(to[i]);
    out[x]=tim;
}
void build() {
    T1.SZ=T1.last=1;
    for(RI i=1;i<=n;++i) T1.ins(S[i]-'a',i);
    for(RI i=2;i<=T1.SZ;++i) add(T1.pre[i],i);
    dfs(1);
    for(RI i=1;i<=T1.SZ;++i)
        if(T1.orz[repos[i]]) chan(rt[i],rt[i-1],1,n,T1.id[repos[i]]);
        else rt[i]=rt[i-1];
}
int check(int x,int l,int r) {return x&&query(rt[in[x]-1],rt[out[x]],l,r,1,n);}
int main()
{
    scanf("%s",S+1),n=strlen(S+1);
    build();
    scanf("%d",&Q);
    while(Q--) {
        int l,r,nowl=0,now=1;
        scanf("%s%d%d",T+1,&l,&r);
        m=strlen(T+1);
        T2.last=T2.SZ=1;
        for(RI i=1;i<=m;++i) T2.ins(T[i]-'a',i);
        for(RI i=1;i<=m;++i) {
            while(1) {
                if(check(T1.ch[now][T[i]-'a'],l+nowl,r))
                    {++nowl,now=T1.ch[now][T[i]-'a'];break;}
                if(!nowl) break;
                --nowl;
                if(nowl==T1.step[T1.pre[now]]) now=T1.pre[now];
            }
            lim[i]=nowl;
        }
        ans=0;
        for(RI i=1;i<=T2.SZ;++i)
            ans+=max(0,T2.step[i]-max(T2.step[T2.pre[i]],lim[T2.id[i]]));
        printf("%lld\n",ans);
        for(RI i=1;i<=T2.SZ;++i)
            for(RI j=0;j<26;++j) T2.ch[i][j]=0;
    }
    return 0;
}