[CF 666E] Forensic Examination

Description

Solution

对 \(T[1..m]\) 建立广义后缀自动机，离线，找出代表 \(S[pl,pr]\) 的每个节点，线段树合并。
Code

#include <cstdio>

#include <vector>

#include <cstring>

#include <algorithm>

const int N = 500005, M = 9500005;

struct Edge {

	int v, nxt;

} e[N];

struct Node {

	int l, r, x, y, id;

	bool operator < (const Node & rhs) const {

		return y < rhs.y;

	}

} a[N];

struct Pair {

	int x, y;

	bool operator < (const Pair & rhs) const {

		return (x == rhs.x && y > rhs.y) || x < rhs.x;

	}

} sum[M], ans[N];

int L[N], q, n, m, mx[N], ch[N][30], sz = 1, las = 1, head[N], tot, fa[N], cnt, ls[M], rs[M], f[20][N], rt[N];

char s[N], t[N];

std::vector<int> b[N];

int read() {

	int x = 0; char c = getchar();

	while (c < '0' || c > '9') c = getchar();

	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();

	return x;

}

void adde(int u, int v) {

	e[++tot].nxt = head[u], head[u] = tot, e[tot].v = v;

}

void ins(int c) {

	int p = las, np = ++sz;

	mx[np] = mx[p] + 1, las = np;

	for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;

	if (!p) { fa[np] = 1; return; }

	int q = ch[p][c];

	if (mx[p] + 1 == mx[q]) { fa[np] = q; return; }

	int nq = ++sz;

	mx[nq] = mx[p] + 1, fa[nq] = fa[q], fa[np] = fa[q] = nq;

	memcpy(ch[nq], ch[q], sizeof ch[q]);

	for (; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;

}

void update(int &x, int l, int r, int p) {

	if (!x) x = ++cnt;

	if (l == r) { sum[x].x = 1, sum[x].y = l; return; }

	int mid = (l + r) >> 1;

	if (p <= mid) update(ls[x], l, mid, p);

	else update(rs[x], mid + 1, r, p);

	sum[x] = std::max(sum[ls[x]], sum[rs[x]]);

}

Pair query(int x, int l, int r, int L, int R) {

	Pair res; res.x = 0, res.y = 0;

	if (!x) return res;

	if (L <= l && r <= R) return sum[x];

	int mid = (l + r) >> 1;

	if (L <= mid) res = query(ls[x], l, mid, L, R);

	if (mid < R) res = std::max(res, query(rs[x], mid + 1, r, L, R));

	return res;

}

int merge(int x, int y) {

	if (!x) return y;

	if (!y) return x;

	if (!ls[x] && !rs[x] && !ls[y] && !rs[y]) { sum[x].x += sum[y].x; return x; }

	ls[x] = merge(ls[x], ls[y]);

	rs[x] = merge(rs[x], rs[y]);

	sum[x] = std::max(sum[ls[x]], sum[rs[x]]);

	return x;

}

void dfs1(int u) {

	f[0][u] = fa[u];

	for (int i = 1; i <= 18; ++i) f[i][u] = f[i - 1][f[i - 1][u]];

	for (int i = head[u]; i; i = e[i].nxt) dfs1(e[i].v);

}

void jump(int x, int k) {

	for (int i = 18; ~i; --i)

		if (mx[f[i][x]] >= a[k].y - a[k].x + 1) x = f[i][x];

	b[x].push_back(k);

}

void dfs2() {

	int x = 1, y = 0;

	for (int i = 1, j = 1; i <= n; ++i) {

		int c = s[i - 1] - 'a';

		while (x && !ch[x][c]) x = fa[x], y = mx[x];

		if (!x) { x = 1, y = 0; continue; }

		++y, x = ch[x][c];

		while (j <= q && a[j].y < i) ++j;

		while (j <= q && a[j].y == i) {

			if (y >= a[j].y - a[j].x + 1) jump(x, j);

			++j;

		}

	}

}

void dfs3(int u) {

	for (int i = head[u]; i; i = e[i].nxt)

		dfs3(e[i].v), rt[u] = merge(rt[u], rt[e[i].v]);

	int sz = b[u].size();

	for (int i = 0; i < sz; ++i) ans[a[b[u][i]].id] = query(rt[u], 1, m, a[b[u][i]].l, a[b[u][i]].r);

}

int main() {

	scanf("%s", s), m = read();

	for (int i = 1; i <= m; ++i) {

		scanf("%s", t), n = strlen(t), las = 1;

		for (int j = 0; j < n; ++j)

			ins(t[j] - 'a'), update(rt[las], 1, m, i);

	}

	q = read(), n = strlen(s);

	for (int i = 1; i <= q; ++i) L[i] = a[i].l = read(), a[i].r = read(), a[i].x = read(), a[i].y = read(), a[i].id = i;

	std::sort(a + 1, a + q + 1);

	for (int i = 2; i <= sz; ++i) adde(fa[i], i);

	dfs1(1), dfs2(), dfs3(1);

	for (int i = 1; i <= q; ++i) printf("%d %d\n", ans[i].y ? ans[i].y : L[i], ans[i].x);

	return 0;

}
巴特西

[CF 666E] Forensic Examination

Description

Solution

Code

最新文章

热门文章
