https://codeforces.com/problemset/problem/906/E
3300
给定字符串 (s,t)，可以翻转 (t) 的若干不相交的区间，使得 (t=s)，求最少翻转几个区间？(|s|,|t|le 5 imes 10^5)
翻转区间相等看起来想一个回文串，我们重新构造，把 (t) 插入 (s)，构造一个 (s[1]t[1]s[2]t[2]...s[n]t[n]) 这样的字符串。然后我们发现题目要求即为最小的偶回文划分。当然相同的部分会形成若干长度为 (2) 的回文串，这时我们需要特殊处理。
具体考虑 dp，设 (f_i) 代表前 (i) 个位置的最小花费。显然有 (f_i=min_{s[j+1...i] is palindrome} f_j + 1)，不过还有第二种转移，在 (s[i]=s[i-1]) 时可以不用任何花费从 (f_{i-2]) 转移过来。然后我们发现前者可以利用回文串 border 的性质优化，就 (O(nlog{n})) 了。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int mark[maxn], pre[maxn], g[maxn], f[maxn], top[maxn], d[maxn], len[maxn], fail[maxn], go[maxn][26], tot, lst;
char t[maxn], tt[maxn], s[maxn];
void build() { s[0] = -1; len[tot = 1] = -1; len[0] = 0; fail[1] = fail[0] = 1; }
int ins(int n, int c) {
int p = lst;
while (s[n - len[p] - 1] != s[n]) p = fail[p];
if (!go[p][c]) {
int v = ++tot, k = fail[p];
len[v] = len[p] + 2;
while (s[n - len[k] - 1] != s[n]) k = fail[k];
fail[v] = go[k][c];
d[v] = len[v] - len[fail[v]];
top[v] = d[v] == d[fail[v]] ? top[fail[v]] : fail[v];
go[p][c] = v;
}
return lst = go[p][c];
}
int main() {
memset(f, 0x3f, sizeof(f));
f[0] = 0;
scanf("%s%s", t + 1, tt + 1);
int Len = strlen(t + 1);
for (int i = 1; i <= Len; i++) s[2 * i - 1] = t[i], s[2 * i] = tt[i];
Len <<= 1; build();
for (int i = 1; i <= Len; i++) {
ins(i, s[i] - 'a');
for (int j = lst; j > 1; j = top[j]) {
g[j] = i - len[top[j]] - d[j];
if (d[j] == d[fail[j]]) {
if (f[g[j]] > f[g[fail[j]]]) {
g[j] = g[fail[j]];
}
}
if (i % 2 == 0) {
if (f[g[j]] + 1 < f[i]) {
f[i] = f[g[j]] + 1;
pre[i] = g[j];
mark[i] = 1;
}
}
}
if (i % 2 == 0) {
if (s[i] == s[i - 1] && f[i - 2] < f[i]) {
f[i] = f[i - 2];
pre[i] = i - 2;
mark[i] = 0;
}
}
}
if (f[Len] >= 0x3f3f3f3f) {
puts("-1");
return 0;
}
printf("%d
", f[Len]);
for (int i = Len; i; i = pre[i]) {
if (mark[i])
printf("%d %d
", pre[i] / 2 + 1, i / 2);
}
return 0;
}
做题的收获？知道了翻转相等和回文串的转化关系；明白了为什么这么转移 (g) 是对的。