Visits: 308

CF666E Forensic Examination

题意

• 给定一个字符串 $s$，以及 $m$ 个字符串 $t_{1 \dots m}$。
• $q$ 次询问，每次询问 $s[p_l:p_r]$ 在字符串 $t_{l\dots r}$ 中的哪个串里作为子串出现的次数最多，如果有多个答案，输出最小的一个。
• $|s|,q \le 5 \times 10^5$，$m,\sum_{i=1}^m |t_i| \le 5 \times 10^4$。

题解

将 $s$ 和 $t_{1\dots m}$ 合成一个字符串，中间用一个其它的分隔符隔开。

设这个新字符串为 $s^\prime$，有 $|s^\prime| = |s| + \sum_{i=1}^{m}|t_i| + m$。

对这个字符串求 SA，则一次询问 $(p_l,p_r,l,r)$ 的答案为：

SA 中 $p_l$ 所在的位置前后 $\operatorname{height}$ 不小于 $p_r – p_l + 1$ 的区间中，每个后缀对应 $t_i$ 的 $i$ 在 $[l,r]$ 中的众数。

如果我们按照 $\operatorname{height}$ 由大到小合并，并建出 kruskal 重构树。

那一次询问就等价于查询一棵子树内颜色在 $[l,r]$ 中的众数，倍增找到子树的根后，线段树合并即可。

总时间复杂度 $\mathcal O(|s^\prime| \log |s^\prime| + q (\log |s^\prime| + \log m))$。

代码

const int N = 6e5 + 7, M = 21;
int n, m, len[N], q;
char s[N], ss[N];
struct SA {
    int n, m = 127, sa[N], rk[N<<1], tp[N<<1], tx[N], he[N];
    char s[N];
    inline void sort() {
        for (int i = 1; i <= m; i++) tx[i] = 0;
        for (int i = 1; i <= n; i++) ++tx[rk[i]];
        for (int i = 1; i <= m; i++) tx[i] += tx[i-1];
        for (int i = n; i; i--) sa[tx[rk[tp[i]]]--] = tp[i];
    }
    inline bool pd(int i, int j, int k) {
        return tp[i] == tp[j] && tp[i+k] == tp[j+k];
    }
    inline void main() {
        for (int i = 1; i <= n; i++) rk[i] = s[i], tp[i] = i;
        sort();
        for (int k = 1, p; p < n; k <<= 1, m = p) {
            p = 0;
            for (int i = 1; i <= k; i++) tp[++p] = n - k + i;
            for (int i = 1; i <= n; i++)
                if (sa[i] > k) tp[++p] = sa[i] - k;
            sort(), swap(rk, tp), rk[sa[1]] = p = 1;
            for (int i = 2; i <= n; i++)
                rk[sa[i]] = p += !pd(sa[i], sa[i-1], k);
        }
    }
    inline void height() {
        for (int i = 1, p = 0; i <= n; i++) {
            if (p) --p;
            int j = sa[rk[i]-1];
            while (s[i+p] == s[j+p]) ++p;
            he[rk[i]] = p;
        }
    }
} sa;
struct T {
    int l, r;
    pi x;
} t[N<<6|1];
int p[N], rt[N<<1], tot, d[N<<1], num, f[N<<1][M], u[N<<1];

int get(int x) {
    return x == u[x] ? x : (u[x] = get(u[x]));
}

inline pi operator + (pi x, pi y) {
    return x.se < y.se ? y : x;
}

int ins(int l, int r, int x) {
    int p = ++tot;
    if (l == r) return t[p].x = mp(x, 1), p;
    int mid = (l + r) >> 1;
    if (x <= mid) t[p].l = ins(l, mid, x);
    else t[p].r = ins(mid + 1, r, x);
    t[p].x = t[t[p].l].x + t[t[p].r].x;
    return p;
}

int merge(int p, int q, int l, int r) {
    if (!p || !q) return p | q;
    int o = ++tot;
    if (l == r) return t[o].x = t[p].x, t[o].x.se += t[q].x.se, o;
    int mid = (l + r) >> 1;
    t[o].l = merge(t[p].l, t[q].l, l, mid);
    t[o].r = merge(t[p].r, t[q].r, mid + 1, r);
    t[o].x = t[t[o].l].x + t[t[o].r].x;
    return o;
}

pi ask(int p, int l, int r, int L, int R) {
    if (l >= L && r <= R) return t[p].x;
    int mid = (l + r) >> 1;
    pi o = mp(0, 0);
    if (L <= mid) o = ask(t[p].l, l, mid, L, R);
    if (R > mid) o = o + ask(t[p].r, mid + 1, r, L, R);
    return o;
}

int main() {
    rds(s, n), rd(m);
    for (int i = 1; i <= m; i++) {
        rds(ss, len[i]);
        for (int j = 1; j <= len[i]; j++) sa.s[++sa.n] = ss[j];
        sa.s[++sa.n] = sa.m, len[i] += len[i-1] + 1;
    }
    for (int i = 1; i <= n; i++) sa.s[++sa.n] = s[i];
    sa.main(), sa.height();
    for (int i = 1; i <= m; i++)
        for (int j = len[i-1] + 1; j < len[i]; j++)
            rt[sa.rk[j]] = ins(1, m, i);
    for (int i = 1; i <= sa.n; i++) p[i] = u[i] = i;
    sort(p + 2, p + sa.n + 1, [](int i, int j) {
        return sa.he[i] > sa.he[j];
    });
    num = sa.n;
    for (int i = 2; i <= sa.n; i++) {
        d[++num] = sa.he[p[i]];
        int x = get(p[i]), y = get(p[i] - 1);
        f[x][0] = f[y][0] = u[x] = u[y] = u[num] = num;
        rt[num] = merge(rt[x], rt[y], 1, m);
    }
    for (int j = 1; j < M; j++)
        for (int i = 1; i <= num; i++)
            f[i][j] = f[f[i][j-1]][j-1];
    rd(q);
    for (int i = 1, l, r, pl, pr; i <= q; i++) {
        rd(l), rd(r), rd(pl), rd(pr);
        int x = sa.rk[pl+len[m]], k = pr - pl + 1;
        for (int j = M - 1; ~j; j--)
            if (d[f[x][j]] >= k) x = f[x][j];
        pi ans = ask(rt[x], 1, m, l, r);
        print(ans.fi ? ans.fi : l, ' '), print(ans.se);
    }
    return 0;
}