sol

关于Sam中串出现次数的问题, 总是与endpos相关.

对于此题, 询问不止一个串.

故, 建立广义后缀自动机.

引入概念

广义后缀自动机: 可识别n个串: s_1, s_2\dots s_n

相当于是s_1+ s_2\dots+ s_n的单个串(‘+’ 表示特殊字符)的Sam

故, 每次读完一个串就将las移到root即可.

但是这样会导致失去原先Sam的一个性质:

  • len(fa)严格小于len(u)

什么意思, 就是出现了无用点

ex : “a” 与 “a”的广义sam

但是父节点依旧是儿子节点的子串(本身也是自己的子串)

回到本题

  1. 建立完了Sam后, 如何寻找询问的串所在自动机上的状态?

    考虑子串可以表示为前缀的后缀

    故对于s[i…j], 预处理出每个位置结尾的前缀的状态

    s[1…j]对应Sam的哪个状态

    接下来就相当于是遍历它到根路径的一个过程, 倍增即可.

  2. 如何处理只有一个串询问

    类似与Bzoj3277, 相当于是O(len)遍历Samlen个前缀.

    如果询问的串的状态点出现在这些状态到根的路径上, 就意味子串出现过.

    (本质还是做子串是前缀的后缀)

  3. 本题求解

    我们发现\sum_i |t_i| \le 5·10^4

    那么可以维护每一个点的right集合

    如果点在串1中出现, 就让cnt[1]++, 串x中出现, 就让cnt[x]++

关于线段树合并的复杂度

  • 本质上开点线段树的点数与所维护的一段段线段的数量是同阶的

考虑两个线段树合并时, 复杂度就是两颗线段树的公共点数

也就是所维护的线段的的长度之和 \cdot \log n.

进一步的, 对于开始是n棵1个点线段树(就算不是显然可以化成这样)

那么显然, 复杂度不会超过n\log n

Code

注意线段树合并吧, 做修改时一定要建新点…

%:pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 1.2e6 + 50;
const int Maxn = 5e5 + 50;

int n, m, t, l, r, ql, qr, I, S, suf[Maxn], li[Maxn / 10];
string s[Maxn / 10];

namespace {
    int cur = 1, id = 1, len[N], fa[N], ch[N][26];
    int p, q, nq, a[N], ton[N], f[N][22];

    inline void copy(int a, int b) {
        fa[a] = fa[b];
        for(int i = 0; i < 26; ++i)
            ch[a][i] = ch[b][i];
    }
    void insert(int c) {
        p = cur, cur = ++id;
        len[cur] = len[p] + 1;
        for(; p && !ch[p][c]; p = fa[p])
            ch[p][c] = cur;
        if(!p) return (void) (fa[cur] = 1);
        q = ch[p][c];
        if(len[q] == len[p] + 1) {
            fa[cur] = q;
        } else {
            copy(nq = ++id, q);
            len[nq] = len[p] + 1;
            fa[q] = fa[cur] = nq;
            for(int u = p; u && ch[u][c] == q; u = fa[u])
                ch[u][c] = nq;
        }
    }
}
void sort() {
    int mx = 0;
    for(int i = 1; i <= id; ++i)
        ++ton[len[i]], mx = max(mx, len[i]);
    for(int i = 1; i <= mx; ++i)
        ton[i] += ton[i - 1];
    for(int i = 1; i <= id; ++i)
        a[ton[len[i]]--] = i;
}
namespace sol {
    int tot, rt[N], ls[N], rs[N], ans[N], cnt[N];

    inline void update(int rt) {
        if(cnt[ls[rt]] >= cnt[rs[rt]]) {
            ans[rt] = ans[ls[rt]];
            cnt[rt] = cnt[ls[rt]];
        } else {
            ans[rt] = ans[rs[rt]];
            cnt[rt] = cnt[rs[rt]];
        }
    }
    void modify(int &rt, int l, int r, int pos) {
        if(!rt) rt = ++tot;
        if(l == r)
            return (void) (ans[rt] = pos, ++cnt[rt]);
        int mid = l + r >> 1;
        if(pos <= mid) modify(ls[rt], l, mid, pos);
        else modify(rs[rt], mid + 1, r, pos);
        update(rt);
    }
    int merge(int u, int v, int l, int r) {
        if(!u || !v) return u + v;
        int res = ++tot, mid = l + r >> 1;
        if(l == r) {
            ans[res] = l;
            cnt[res] = cnt[u] + cnt[v];
            return res;
        }
        ls[res] = merge(ls[u], ls[v], l, mid);
        rs[res] = merge(rs[u], rs[v], mid + 1, r);
        update(res);
        return res;
    }
    int calc(int u, int w) {
        for(int i = 21; ~i; --i) {
            if(len[f[u][i]] >= w)
                u = f[u][i];
        } return u;
    }
    void query(int rt, int l, int r, int L, int R) {
        if(l > R || r < L) return ;
        if(l >= L && r <= R) {
            if(cnt[rt] > S)
                I = ans[rt], S = cnt[rt];
            return ;
        }
        int mid = l + r >> 1;
        query(ls[rt], l, mid, L, R);
        query(rs[rt], mid + 1, r, L, R);
    }
    void main() {
        int u = 1; 
        for(int i = 0; i < n; ++i)
            suf[i] = u = ch[u][s[0][i] - 'a'];
        for(int i = 1; i <= m; ++i) {
            u = 1;
            for(int j = 0; j < li[i]; ++j) {
                u = ch[u][s[i][j] - 'a'];
                modify(rt[u], 1, m, i);
            }
        }
        sort();
        for(int i = 0; i < 22; ++i)
            f[1][i] = 1;
        for(register int i = 2; i <= id; ++i) {
            int u = a[i];
            f[u][0] = fa[u];
            for(int j = 1; j < 22; ++j)
                f[u][j] = f[f[u][j - 1]][j - 1];
        }
        for(int i = id; i; --i) 
            rt[fa[a[i]]] = merge(rt[fa[a[i]]], rt[a[i]], 1, m);
    }
}
int main() {
    cin >> s[0] >> m;
    n = s[0].length();
    for(int i = 0; i < n; ++i) 
        insert(s[0][i] - 'a');
    for(int i = 1; i <= m; ++i) {
        cin >> s[i], cur = 1;
        li[i] = s[i].length();
        for(int j = 0; j < li[i]; ++j) 
            insert(s[i][j] - 'a');
    }   
    sol :: main();
    for(cin >> t; t--; ) {
        scanf("%d%d%d%d", &l, &r, &ql, &qr);
        --qr, --ql;
        int node = sol :: calc(suf[qr], qr - ql + 1);
        I = S = 0;
        sol :: query(sol :: rt[node], 1, m, l, r);
        if(!S) I = l;
        printf("%d %d\n", I, S);
    }
    return 0;
}