Luogu

LOJ

分析

先考虑 $l=1,r=|S|$ 的情况。

对 $S$ 和 $T$ 建 SAM。

设 $lim_i$ 表示 $T[1..i]$ 最长的是 $S$ 的子串的后缀的长度，可以在 $S$ 的 SAM 的 Parent 树上跳来求出：

• 如果有对应的转移直接走过去，匹配长度加 $1$；
• 否则跳 Parent 树，直到某个点有对应的转移，匹配长度变为该点的 $len$；
• 如果跳到 $1$ 都没有对应的转移，匹配长度为 $0$。

设 $pos_i$ 表示 $T$ 的 SAM 的 $i$ 节点对应的 $endpos$ 集合中最小的元素，可以在建 SAM 时顺便维护。

则不难得到答案为（这里的 $len_i$ 是 $T$ 的 SAM 对应的 $len_i$）
$$
\sum_{i=2}^{cnt}\max\left\{0,len_i-\max\left\{len_{fa_i},lim_{pos_i}\right\}\right\}
$$
现在考虑 $l,r$ 任意的情况。上面做法的问题是求 $lim$ 时跳到的点不一定在 $S[l..r]$ 中。于是我们用线段树合并求出 $S$ 的 SAM 中每个点的 $endpos$ 集合，这样子跳的时候判断一下当前节点是否在 $[l+len,r]$ 中出现过即可（这里的 $len$ 是已经匹配的长度）。

其实还挺好写的（

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;

int n,m; char s[N],t[N];

namespace T {
#define ls(o) t[o].ls
#define rs(o) t[o].rs
    int rt[N],tot=0;
    struct node { int ls,rs; } t[N*30];
    void modify(int& o,int l,int r,int p) {
        if (!o) o=++tot;
        if (l==r) return;
        int mid=(l+r)>>1;
        if (p<=mid) modify(ls(o),l,mid,p);
        else modify(rs(o),mid+1,r,p);
    }
    int merge(int x,int y) {
        if (!x||!y) return x+y;
        int o=++tot;
        ls(o)=merge(ls(x),ls(y));
        rs(o)=merge(rs(x),rs(y));
        return o;
    }
    bool query(int o,int l,int r,int ql,int qr) {
        if (!o) return 0;
        if (ql<=l&&r<=qr) return 1;
        int mid=(l+r)>>1; bool res=0;
        if (ql<=mid) res|=query(ls(o),l,mid,ql,qr);
        if (qr>mid) res|=query(rs(o),mid+1,r,ql,qr);
        return res;
    }
#undef ls
#undef rs
}

namespace SAM_S {
    int last=1,cnt=1;
    int ch[N][26],fa[N],len[N];
    void extend(int c,int pos) {
        int p=last,np=++cnt; last=cnt,len[np]=len[p]+1;
        for (;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
        if (!p) fa[np]=1;
        else {
            int q=ch[p][c];
            if (len[p]+1==len[q]) fa[np]=q;
            else {
                int nq=++cnt; len[nq]=len[p]+1;
                memcpy(ch[nq],ch[q],sizeof(ch[q]));
                fa[nq]=fa[q],fa[q]=fa[np]=nq;
                for (;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
            }
        }
        T::modify(T::rt[last],1,n,pos);
    }

    vector<int> E[N];
    void dfs(int u) {
        for (int v:E[u]) dfs(v),T::rt[u]=T::merge(T::rt[u],T::rt[v]);
    }

    void build() {
        for (int i=1;i<=n;++i) extend(s[i]-'a',i);
        for (int i=2;i<=cnt;++i) E[fa[i]].emplace_back(i);
        dfs(1);
    }
}

namespace SAM_T {
    int last,cnt;
    int ch[N][26],fa[N],len[N],lim[N],pos[N];
    int newnode() {
        ++cnt; fa[cnt]=len[cnt]=pos[cnt]=0;
        memset(ch[cnt],0,sizeof(ch[cnt]));
        return cnt;
    }
    void init() { cnt=0,last=newnode(); }
    void extend(int c) {
        int p=last,np=newnode(); last=cnt,pos[np]=len[np]=len[p]+1;
        for (;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
        if (!p) fa[np]=1;
        else {
            int q=ch[p][c];
            if (len[p]+1==len[q]) fa[np]=q;
            else {
                int nq=newnode(); len[nq]=len[p]+1;
                memcpy(ch[nq],ch[q],sizeof(ch[q]));
                pos[nq]=pos[q],fa[nq]=fa[q],fa[q]=fa[np]=nq;
                for (;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
            }
        }
    }

    ll calc() {
        ll res=0;
        for (int i=2;i<=cnt;++i)
            res+=max(0,len[i]-max(len[fa[i]],lim[pos[i]]));
        return res;
    }
}

int main() {
    scanf("%s",s+1); n=strlen(s+1);
    SAM_S::build();
    int T=read();
    while (T--) {
        SAM_T::init();
        scanf("%s",t+1); m=strlen(t+1);
        int L=read(),R=read();
        for (int i=1,u=1,l=0;i<=m;++i) {
            int c=t[i]-'a';
            SAM_T::extend(c);
            while (1) {
                if (SAM_S::ch[u][c]&&T::query(T::rt[SAM_S::ch[u][c]],1,n,L+l,R)) {
                    ++l,u=SAM_S::ch[u][c]; break;
                }
                if (!l) break;
                --l;
                if (l==SAM_S::len[SAM_S::fa[u]]) u=SAM_S::fa[u];
            }
            SAM_T::lim[i]=l;
        }
        printf("%lld\n",SAM_T::calc());
    }
    return 0;
}