CF666E Forensic Examination 题解

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]$ 中的众数，倍增找到子树的根后，线段树合并即可。

代码

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;
}

题意

题解

代码

评论