题解 CF666E 【Forensic Examination】

> [CF666E Forensic Examination](https://codeforces.com/contest/666/problem/E) ## 题意 - 给定一个字符串 $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))$。 ## 代码 ```cpp 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; } ```