Gym 100543G Virus synthesis 题解

laijinyi / 2024-10-07 / 原文

Solution

首先只考虑回文串的答案；我们重点考虑的是偶回文串

结论：对于偶回文串 $u$，从其最长的长度小于等于他的一半的回文后缀，或其父亲转移过来，一定是最优的

证明：

设 $u$ 的一个回文子串为 $v$（不是父亲），你要让 $v\to u$ 的转移最优

首先 $v$ 不能跨过 $u$ 的中点，因为此时“从父亲转移过来”一定不会更劣

其次 $v$ 不能位于 $u$ 的中间（非前后缀），因为这种情况 $u$ 的祖先已经考虑到了

证完了

于是转移即可；对于奇回文串，他只能从其父亲或 fail 转移而来，证明是类似的。

做完了。

Code

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 1e5 + 10;
string s;
int n;

int cur, last, sz, len[N], fail[N], nxt[N][4], f[N], half[N];
void init() {
	while (sz >= 0) {
		len[sz] = fail[sz] = f[sz] = half[sz] = 0;
		rep(i, 0, 3) nxt[sz][i] = 0;
		--sz;
	}
	cur = last = 0, sz = 1, len[1] = -1, fail[0] = 1;
}
int getfail(int u, int i) {
	while (i - len[u] - 1 < 0 || s[i - len[u] - 1] != s[i]) u = fail[u];
	return u;
}
void Solve() {
	cin >> s, n = s.length(), init();
	int ans = 114514;
	auto Get = [&](char c) {
		if (c == 'A') return 0;
		if (c == 'G') return 1;
		if (c == 'T') return 2;
		if (c == 'C') return 3;
		return 0;
	};
	rep(i, 0, n - 1) {
		int p = getfail(last, i), ch = Get(s[i]);
		if (!nxt[p][ch]) {
			cur = ++sz;
			fail[cur] = nxt[getfail(fail[p], i)][ch];
			nxt[p][ch] = cur;
			len[cur] = len[p] + 2;
			if (len[cur] & 1) {
				f[cur] = min(f[p] + 2, f[fail[cur]] + len[cur] - len[fail[cur]]);
			} else {
				int q = getfail(half[p], i);
				while (len[q] + 2 > len[cur] / 2) q = getfail(fail[q], i);
				if (len[cur] > 2 && (q || s[i] == s[i - 1])) q = nxt[q][ch];
				else q = 0;
				half[cur] = q;
				if (p) {
					f[cur] = min(f[p] + 1, f[half[cur]] + len[cur] / 2 - len[half[cur]] + 1);
				} else {
					f[cur] = 2;
				}
			}
			ans = min(ans, n - len[cur] + f[cur]);
		}
		last = nxt[p][ch];
	}
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int t;
	cin >> t;
	while (t--) Solve();
	return 0;
}