Codeforces

Luogu

分析

先对 $T_{1..m}$ 建立广义 SAM，然后把 $S$ 丢上去匹配，记录每个前缀匹配到的节点 $pos_i$。

考虑对每个节点维护一棵以 $T$ 的下标为下标的线段树，线段树上的每个节点维护当前串在这些 $T$ 串中的出现次数的最大值及其下标。这可以通过线段树合并预处理出来。

询问时，我们首先找到 $s_{l..r}$ 所在的节点，直接从 $pos_r$ 向上倍增即可。然后在这个节点上查询区间最大值即可。

注意特判最多的出现次数为 $0$ 的情况。

代码

// ====================================
//   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)
#define debug(...) fprintf(stderr,__VA_ARGS__)
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=500000+10;

int n,m,Q,ppos[N],plen[N];
char s[N],t[N];

namespace H { // Segment Tree
#define ls(o) t[o].lc
#define rs(o) t[o].rc
    struct data {
        int c,p;
        data(int c_=0,int p_=0): c(c_),p(p_) {}
    };
    bool operator <(data a,data b) {
        if (a.c!=b.c) return a.c<b.c;
        else return a.p>b.p;
    }
    bool operator >(data a,data b) { return b<a; }

    struct node {
        int lc,rc; data w;
        node(int l=0,int r=0,data w_=data()): lc(l),rc(r),w(w_) {}
    } t[N*60];
    int rt[N],tot=0;

    void pushup(int o) { t[o].w=max(t[ls(o)].w,t[rs(o)].w); }
    void modify(int &o,int l,int r,int p) {
        if (!o) o=++tot;
        if (l==r) { ++t[o].w.c,t[o].w.p=p; return; }
        int mid=(l+r)>>1;
        if (p<=mid) modify(ls(o),l,mid,p);
        else modify(rs(o),mid+1,r,p);
        pushup(o);
    }
    data query(int o,int l,int r,int ql,int qr) {
        if (!o) return data();
        if (ql<=l&&r<=qr) return t[o].w;
        int mid=(l+r)>>1; data res;
        if (ql<=mid) res=max(res,query(ls(o),l,mid,ql,qr));
        if (qr>mid) res=max(res,query(rs(o),mid+1,r,ql,qr));
        return res;
    }
    int merge(int x,int y,int l,int r) {
        if (!x||!y) return x+y;
        int o=++tot;
        if (l==r) { t[o].w.c=t[x].w.c+t[y].w.c,t[o].w.p=l; return o; }
        int mid=(l+r)>>1;
        ls(o)=merge(ls(x),ls(y),l,mid),rs(o)=merge(rs(x),rs(y),mid+1,r);
        pushup(o); return o;
    }
#undef ls
#undef rs
}
using H::rt;

namespace S { // Suffix Automaton
    int ch[N][26],fa[N],len[N],tot=1;
    int extend(int c,int p) {
        int np=++tot; 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=++tot; 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;
            }
        }
        return np;
    }

    vector<int> E[N];
    int f[19][N];
    void dfs(int u,int fa) {
        f[0][u]=fa;
        for (int i=1;i<19;++i) f[i][u]=f[i-1][f[i-1][u]];
        for (int v:E[u]) dfs(v,u),rt[u]=H::merge(rt[u],rt[v],1,m);
    }
    int jump(int u,int l) {
        for (int i=18;~i;--i)
            if (len[f[i][u]]>=l) u=f[i][u];
        return u;
    }
}

namespace T { // Trie
    int ch[N][26],fa[N],c[N],pos[N],tot=1;
    vector<int> vec[N];
    void insert(char *s,int id) {
        int l=strlen(s+1),u=1;
        for (int i=1;i<=l;++i) {
            int w=s[i]-'a';
            if (!ch[u][w]) ch[u][w]=++tot,fa[tot]=u,c[tot]=w;
            u=ch[u][w],vec[u].emplace_back(id);
        }
    }
    void build() {
        queue<int> Q;
        for (int i=0;i<26;++i) if (ch[1][i]) Q.emplace(ch[1][i]);
        pos[1]=1;
        while (!Q.empty()) {
            int u=Q.front(); Q.pop();
            pos[u]=S::extend(c[u],pos[fa[u]]);
            for (int i:vec[u]) H::modify(rt[pos[u]],1,m,i);
            for (int i=0;i<26;++i) if (ch[u][i]) Q.emplace(ch[u][i]);
        }
    }
}

int main() {
    scanf("%s",s+1),n=strlen(s+1);
    m=read();
    for (int i=1;i<=m;++i) scanf("%s",t+1),T::insert(t,i);
    T::build();
    for (int i=2;i<=S::tot;++i) S::E[S::fa[i]].emplace_back(i);
    S::dfs(1,0);
    for (int i=1,u=1,l=0;i<=n;++i) {
        int w=s[i]-'a';
        while (u&&!S::ch[u][w]) u=S::fa[u],l=S::len[u];
        if (!u) u=1,l=0;
        if (S::ch[u][w]) u=S::ch[u][w],++l;
        ppos[i]=u,plen[i]=l;
    }
    Q=read();
    while (Q--) {
        int l=read(),r=read(),pl=read(),pr=read();
        if (pr-pl+1>plen[pr]) { printf("%d 0\n",l); continue; }
        int u=S::jump(ppos[pr],pr-pl+1);
        H::data t=H::query(rt[u],1,m,l,r);
        printf("%d %d\n",t.c?t.p:l,t.c);
    }
    return 0;
}