CF590E Birthday 题解

CF590E Birthday

题意

• 给定 $n$ 个仅包含 a,b 的字符串。
• 你需要去掉尽可能少的字符串，使得剩下的字符串中不存在某一个串是另一个串的子串。
• $n \le 750$，$\sum_{i=1}^n |s_i| \le 10^7$。

题解

设 $\sum_{i=1}^n |s_i| = m$。

首先可以 $\mathcal O(m)$ 建 AC 自动机然后求出所有的子串关系。

显然我们不能暴力跳 fail，这样显然会 T 飞。

注意到子串关系是一个偏序关系，因此我们只需要跳到最近的结尾同时路径压缩即可，那么此时可以建出一个 DAG。

接下来就是 P4298 [CTSC2008]祭祀了，不过还是在这儿完整的写一遍。

题目要求的实际上是这个偏序关系的最长反链，通过 Dilworth 定理可以发现就是 DAG 的最小可重复路径点覆盖。

最小可重复路径点覆盖又可以通过 $\mathcal O(n^3)$ 的传递闭包转化为最小路径点覆盖。

又 DAG 的最小路径点覆盖包含的路径条数 $= n -$ 其拆点二分图的最大匹配数。

使用匈牙利算法即可在 $\mathcal O(n^3)$ 的时间求出答案。

接下来的问题是如何构造方案。

我们先求出传递闭包后的图的最小路径点覆盖包含的路径集合 $path$：

1. 设在拆点二分图中左部点 $x$ 对应的右部点为 $x^{\prime}$，若 $x,y$ 匹配则有 $f_x = y, f_y = x$。
2. 依次考虑左部的每一个非匹配点 $x_0$。
3. 从 $x_0$ 出发，每次从 $x$ 走到 $f_{x^{\prime}}$，直至到达一个左部点 $y_0$，满足 $y_0^{\prime}$ 是非匹配点。
4. 那么经过的所有点构成一条以 $y_0$ 为起点 $x_0$ 为终点的路径。

接下来我们要从 $path$ 的每条路径上选出一个点构成原图的最长反链：

1. 将所有的终点 $x_0$ 放到一起构成一个集合 $E$。
2. 求出从 $E$ 中的所有节点出发，走一条边，到达的所有节点 $next(E)$。
3. 根据传递闭包的性质，若 $E$ 与 $next(E)$ 没有交，那么 $E$ 即为所求。
4. 否则考虑 $E \cap next(E)$ 的所有节点 $e$，沿着 $e$ 所在的路径反着走，直到一个节点 $e^{\prime} \notin next(E)$，在 $E$ 中将 $e$ 替换为 $e^{\prime}$。
5. 回到第 $3$ 步。

总时间复杂度 $\mathcal O(m + n^3)$。

注意本题任何与 AC 自动机相关的递归均会爆栈。

代码

const int N = 757, M = 1e7 + 7;
int n, len[N], ed[N], trie[M][2], fail[M], fa[M], gt[M], tot = 1;
int d[N][N], v[N], f[N];
char s[M];
queue<int> q;

bool dfs(int x) {
	for (int i = 1; i <= n; i++)
		if (d[x][i] && !v[i]) {
			v[i] = 1;
			if (!f[i] || dfs(f[i])) return (f[i] = x);
		}
	return 0;
}

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) {
		rds(s, len[i]);
		int p = 1;
		for (int j = 1; j <= len[i]; j++) {
			int c = s[j] - 'a';
			if (!trie[p][c]) trie[p][c] = ++tot, fa[tot] = p;
			p = trie[p][c];
		}
		ed[i] = p, gt[p] = i;
	}
	for (int i = 0; i < 2; i++)
		if (trie[1][i]) fail[trie[1][i]] = 1, q.push(trie[1][i]);
		else trie[1][i] = 1;
	while (q.size()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < 2; i++)
			if (trie[x][i])
				fail[trie[x][i]] = trie[fail[x]][i], q.push(trie[x][i]);
			else trie[x][i] = trie[fail[x]][i];
	}
	gt[1] = -1;
	vi o;
	for (int i = 1; i <= n; i++)
		for (int j = ed[i]; j != 1; j = fa[j]) {
			int x = fail[j];
			o.clear();
			while (!gt[x]) o.pb(x), x = fail[x];
			while (o.size()) fail[o.back()] = x, o.pop_back();
			fail[j] = x;
			if (j != ed[i] && gt[j]) x = j;
			if (x != 1) d[i][gt[x]] = 1;
		}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				d[i][j] |= d[i][k] & d[k][j];
	for (int i = 1; i <= n; i++) d[i][i] = 0;
	int ans = n;
	for (int i = 1; i <= n; i++) ans -= dfs(i), memset(v, 0, sizeof(v));
	print(ans);
	for (int i = 1; i <= n; i++) v[f[i]] = 1;
	vi s;
	for (int i = 1; i <= n; i++) if (!v[i]) s.pb(i);
	memset(v, 0, sizeof(v));
	bool ok = 1;
	while (ok) {
		ok = 0;
		for (int x : s)
			for (int y = 1; y <= n; y++)
				if (d[x][y]) v[y] = 1;
		for (int &x : s)
			if (v[x]) {
				ok = 1;
				while (v[x]) x = f[x];
			}
	}
	for (auto x : s) print(x, ' ');
	return 0;
}