就是匹配那段，本来 WA#22 改后直接 T 了

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>

#define N 500010
#define LL long long

using namespace std;
int n;
string S,T;

int tcnt,rt[N<<1];
struct Tree { int ls,rs; }t[N<<6];

void upd(int &x,int l,int r,int pos) {
    if (!x) x=++tcnt;
    if (l==r) return;
    int mid=(l+r>>1);
    if (pos<=mid) upd(t[x].ls,l,mid,pos);
    else upd(t[x].rs,mid+1,r,pos);
}

int merge(int x,int y,int l,int r) {
    if (!x or !y) return x|y;
    int rt=++tcnt;
    if (l==r) return rt;
    int mid=(l+r>>1);
    t[rt].ls=merge(t[x].ls,t[y].ls,l,mid);
    t[rt].rs=merge(t[x].rs,t[y].rs,mid+1,r);
    return rt;
}

bool ask(int x,int l,int r,int L,int R) {
    if (!x or L>R) return 0;
    if (L<=l and r<=R) return 1;
    int mid=(l+r>>1);
    if (R<=mid) return ask(t[x].ls,l,mid,L,R);
    else if (L>mid) return ask(t[x].rs,mid+1,r,L,R);
    else return ask(t[x].ls,l,mid,L,R)|ask(t[x].rs,mid+1,r,L,R);
}

struct SAM {
    int tot=1,np=1,len[N<<2],fail[N<<2],ch[N<<2][26],ans[N<<2];

    void ins(int c,int op=0) {
        int p=np; len[np=++tot]=len[p]+1;
        if (op) upd(rt[np],1,n,op);
        while (p and !ch[p][c]) ch[p][c]=np,p=fail[p];
        if (!p) fail[np]=1;
        else {
            int q=ch[p][c];
            if (len[q]==len[p]+1) fail[np]=q;
            else {
                int nq=++tot;
                fail[nq]=fail[q],len[nq]=len[p]+1;
                fail[np]=fail[q]=nq;
                memcpy(ch[nq],ch[q],sizeof ch[q]);
                while (p and ch[p][c]==q) ch[p][c]=nq,p=fail[p];
            }
        }
    }

    void clear() {
        for (int i=1;i<=tot;i++) {
            len[i]=fail[i]=ans[i]=0;
            memset(ch[i],0,sizeof ch[i]);
        }
        tot=np=1;
    }
    
    int cnt,head[N<<2];
    struct Node { int to,nxt; }e[N<<2];

    void add(int u,int v) { e[++cnt]=Node{v,head[u]},head[u]=cnt; }

    void link() {
        for (int i=1;i<=tot;i++) head[i]=0; cnt=0;
        for (int i=2;i<=tot;i++) add(fail[i],i);
    } 

    void dfs0(int u) {
        for (int i=head[u];i;i=e[i].nxt) {
            int v=e[i].to;
            dfs0(v);
            rt[u]=merge(rt[u],rt[v],1,n);
        }
    }

    LL dfs1(int u) {
        LL res=0;
        for (int i=head[u];i;i=e[i].nxt) {
            int v=e[i].to;
            res+=dfs1(v);
            ans[u]=max(ans[u],ans[v]);
        }
        return res+=max(0,len[u]-max(len[fail[u]],ans[u]));
    }
}s1,s2;

int pos[N<<1];

int main() {
    cin>>S; n=S.size(); S=" "+S;
    for (int i=1;i<=n;i++) s1.ins(S[i]-'a',i);
    s1.link(); s1.dfs0(1);
    // cout<<ask(rt[1],1,n,1,n)<<'\n';
    int q; scanf("%d",&q);
    for (int i=1,l,r;i<=q;i++) {
        cin>>T; T=" "+T; s2.clear();
        scanf("%d%d",&l,&r);
        for (int j=1;j<T.size();j++) s2.ins(T[j]-'a');
        s2.link();
        pos[0]=1;
        for (int j=1;j<T.size();j++) pos[j]=s2.ch[pos[j-1]][T[j]-'a'];
        // for (int j=1;j<T.size();j++) printf("%d ",pos[j]); printf("\n");
        int p=1,len=0;
        for (int j=1;j<T.size();j++) {
            if (s1.ch[p][T[j]-'a'] and ask(rt[s1.ch[p][T[j]-'a']],1,n,l+len,r)) p=s1.ch[p][T[j]-'a'],len++;
            else {
                while (p and !(s1.ch[p][T[j]-'a'] and ask(rt[s1.ch[p][T[j]-'a']],1,n,l+len,r))) {
                    len--;
                    if (len==s1.len[s1.fail[p]]) p=s1.fail[p];
                }
                if (!p) p=1,len=0;
                else len++,p=s1.ch[p][T[j]-'a'];
            }
            // printf("%d: %d\n",i,len);
            s2.ans[pos[j]]=max(s2.ans[pos[j]],len);
        }
        printf("%lld\n",s2.dfs1(1));
    }
    return 0;
}