1. 题目

传送门=￣ω￣=

翻译：

给你一个串 $S$以及一个字符串数组 $T[1..m]$，$q$次询问，每次问 $S$的子串 $S[p_l..p_r]$在 $T[l..r]$中的哪个串里的出现次数最多，并输出出现次数。

如有多解输出最靠前的那一个。

$|S| \leq 5 \times 10 ^ 5, q \leq 5 \times 10 ^ 5, m \leq 5 \times 10 ^ 4, \sum |T _ i| \leq 5 \times 10 ^ 4$

2. 题解

这题还是比较毒瘤的。。。感谢 boshi 的全程指导

首先可以想到对 $m$个串 $T _ i$建一个广义后缀自动机，然后每个点搞一个值域为 $[1, m]$的线段树维护该点所代表的等价类里的子串在每个 $T$中的出现次数，$T _ x = T _ {s1} \cup T _ {s2} \cup T _ {s3} …$（其中 $s1,s2,s3…$是 $x$在 pre 树上的子节点），这个用线段树合并搞就行了。

然后询问可以做到在线的，预处理出每个前缀对应的节点以及每个前缀在自动机内的最大匹配长度。

询问一个子串就是一个前缀的一个后缀，确定了前缀对应的节点再倍增找其 pre 树上子串对应的节点就行了，再用最大匹配长度等条件判断一下。

就。。。没了，复杂度 $O(n log n)$

细节很多，贼毒瘤。。。

我的代码应该算短的了而且常数还挺小的，可以参考一下 QwQ

#include <bits/stdc++.h>

#define NS (500005)
#define MS (100005)
#define LGS (16)
#define FIR first
#define SEC second

using namespace std;

typedef pair<int, int> PII;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, pnod[NS], plen[NS], Q;

char Sup[NS], str[MS];

int ls[MS * 40], rs[MS * 40], tsz;

PII tr[MS * 40];

void add(int x, int l, int r, int& a)
{
    if (!a) a = ++tsz;
    tr[a].FIR = 1, tr[a].SEC = x;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (x <= mid) add(x, l, mid, ls[a]);
    else add(x, mid + 1, r, rs[a]);
}

void merge(int& x, int& y, int l, int r)
{
    if (!x) {x = y; return;}
    if (!y) return;
    tr[++tsz] = tr[x], ls[tsz] = ls[x], rs[tsz] = rs[x], x = tsz;
    if (l == r) {tr[x].FIR += tr[y].FIR; return;}
    int mid = (l + r) >> 1;
    merge(ls[x], ls[y], l, mid), merge(rs[x], rs[y], mid + 1, r);
    if (tr[ls[x]].FIR >= tr[rs[x]].FIR)
        tr[x] = tr[ls[x]];
    else tr[x] = tr[rs[x]];
}

PII query(int l, int r, int L, int R, int a)
{
    if (l <= L && R <= r) return tr[a];
    PII res(0, 0);
    int Mid = (L + R) >> 1;
    if (l <= Mid) res = query(l, r, L, Mid, ls[a]);
    if (r > Mid)
    {
        PII tmp = query(l, r, Mid + 1, R, rs[a]);
        if (tmp.FIR > res.FIR) res = tmp;
    }
    return res;
}

struct N
{
    int nxt[26], fa, mxl, root;
    int& operator [] (const char c) {return nxt[c - 'a'];}
} e[MS];

struct SAM
{
    int sz, lst, pre[MS][LGS + 1];
    vector<int> g[MS];
    SAM() {sz = lst = 1;}
    void insert(char c, int id)
    {
        int a = ++sz, p = lst;
        add(id, 1, m, e[a].root), e[a].mxl = e[p].mxl + 1, lst = a;
        while (p && !e[p][c]) e[p][c] = a, p = e[p].fa;
        if (!p) {e[a].fa = 1; return;}
        int q = e[p][c];
        if (e[q].mxl == e[p].mxl + 1) {e[a].fa = q; return;}
        int nq = ++sz;
        e[nq] = e[q], e[nq].mxl = e[p].mxl + 1, e[nq].root = 0;
        e[a].fa = e[q].fa = nq;
        while (e[p][c] == q) e[p][c] = nq, p = e[p].fa;
    }
    void buildg()
    {
        for (int i = 2; i <= sz; i += 1) g[e[i].fa].push_back(i);
    }
    void init(int a, int fa)
    {
        pre[a][0] = fa;
        for (int i = 1; i <= LGS; i += 1)
            pre[a][i] = pre[pre[a][i - 1]][i - 1];
        for (int i = 0; i < g[a].size(); i += 1)
            init(g[a][i], a), merge(e[a].root, e[g[a][i]].root, 1, m);
    }
    void pre_init()
    {
        for (int i = 1, cur = 1, len = 0; i <= n; i += 1)
        {
            while (cur != 1 && !e[cur][Sup[i]])
                cur = e[cur].fa, len = min(len, e[cur].mxl);
            if (e[cur][Sup[i]]) cur = e[cur][Sup[i]], len++;
            pnod[i] = cur, plen[i] = len;
        }
    }
    void Query()
    {
        int l, r, pl, pr, a;
        IN(l), IN(r), IN(pl), IN(pr), a = pnod[pr];
        if (plen[pr] < pr - pl + 1) {printf("%d 0\n", l); return;}
        for (int i = LGS; i >= 0; i -= 1)
            if (e[pre[a][i]].mxl >= pr - pl + 1)
                a = pre[a][i];
        if (e[a].mxl < pr - pl + 1) {printf("%d 0\n", l); return;}
        PII res = query(l, r, 1, m, e[a].root);
        if (!res.FIR) printf("%d 0\n", l);
        else printf("%d %d\n", res.SEC, res.FIR);
    }
} sam;

int main(int argc, char const* argv[])
{
    scanf("%s", Sup + 1), n = strlen(Sup + 1), IN(m);
    for (int i = 1, len; i <= m; i += 1)
    {
        scanf("%s", str + 1), len = strlen(str + 1), sam.lst = 1;
        for (int j = 1; j <= len; j += 1) sam.insert(str[j], i);
    }
    sam.buildg(), sam.init(1, 0), sam.pre_init();
    IN(Q); while (Q--) sam.Query();
    return 0;
}