网上题解都在说什么啊……

题意

BZOJ 4044 & BZOJ 4163：

初始有一个空串，利用下面的操作构造给定串 $S$。

1. 串开头或末尾加一个字符

2. 串开头或末尾加一个该串的逆串

最小化操作数，$|S| \leq 10^5$。

分析

操作 2 会生成长度为偶数的回文串，而一个字符串的本质不同回文子串个数是 $\mathcal{O}(|S|)$ 的，尝试将操作步骤按照操作 2 进行划分。

在最后一次使用操作 2 后，只会在偶回文子串的两端添加字符，设 $f(T)$ 表示构造偶回文子串 $T$ 的最小操作数，则对于初始的空串 $\epsilon$ 有 $f(\epsilon) = 0$，而答案 $\mathrm{ans}$ 为 $\mathop{\min}\limits_{T \in \mathrm{substring}(S)}\{f(T) + |S| - |T|\}$。

如果从未使用操作 2，则类似地有 $f(T) \leq |T|$ 和 $\mathrm{ans} \leq |S|$。

在第一次使用操作 2 前，只会通过添加字符获得偶回文子串的前一半，即 $f(T) \leq \dfrac{|T|}{2} + 1$。

在相邻两次操作 2 之间，有可能在偶回文子串 $P$ 的两端添加字符，再通过操作 2 变成 $T$，其中 $P$ 是 $T$ 的前半部分的子串（也是后半部分的）。

如果 $P$ 不是 $T$ 的前缀，那么一定是在 $P$ 的前端增加了字符。去掉生成 $T$ 的最后一次操作 1 而保留之后的操作 2，则可以用 $P$ 生成字符串 $T'$，其中 $T'$ 是 $T$ 去掉首尾各一个字符组成的串。这意味着，如果生成 $T'$ 经过至少一次操作 2，即 $T' \neq \epsilon$，那么有 $f(T) \leq f(T') + 1$。

如果 $P$ 是 $T$ 的前缀，那么 $P$ 是 $T$ 的 border，在 $P$ 的后端增加字符后使用一次操作 2 可以得到 $T$。事实上，$P$ 是 $T$ 的前半部分中最长的偶 border，因为更短的 border 只会使得操作 1 的操作次数增多。因此可以找到 $T$ 的长度不超过 $\dfrac{|T|}{2}$ 的最长 border $P'$，找到 $P'$ 的最长偶 border $P$，那么有 $f(T) \leq f(P) + \dfrac{|T|}{2} - |P| + 1$。

事实上，不需要找到 $P'$ 的最长偶 border $P$。如果 $P'$ 不是 $T$ 的偶 border，那么构造 $T'$ 的最优操作一定会是使用 $P$ 构造的，直接忽略不是 $P'$ 的长度不是偶数的转移即可。

附：一个串的 border 既是它的前缀又是它的后缀，一个串的 border 的 border 也是这个串的 border。

综上所述，我们可以对 $S$ 构建回文树，对每个状态维护长度不超过一半的最长 border，并进行 DP，时间复杂度 $\mathcal{O}(|S|)$。

代码

贴一个 BZOJ 4044 的代码仅供交流学习。

#include <bits/stdc++.h>
using namespace std;
const int maxn = (int)1e5 + 3, maxc = 4;
int t, n, tot, cur, len[maxn], fail[maxn], nxt[maxn][maxc + 1];
char buf[maxn], str[maxn];
int newNode(int length, int prev = 0) {
    len[tot] = length;
    fail[tot] = prev;
    memset(nxt[tot], 0, sizeof nxt[0]);
    return tot++;
}
void init() {
    n = tot = 0;
    cur = newNode(0);
    fail[cur] = newNode(-1, cur);
    buf[0] = '\0';
}
int slen, trans[257], half[maxn], f[maxn], ans;
void append(char ch) {
    int o = trans[buf[++n] = ch];
    for( ; buf[n - len[cur] - 1] != buf[n]; cur = fail[cur]);
    if(!nxt[cur][o]) {
        int p = newNode(len[cur] + 2), q;
        for(q = fail[cur]; buf[n - len[q] - 1] != buf[n]; q = fail[q]);
        fail[p] = nxt[q][o];
        fa[p] = cur;
        for(q = half[cur]; buf[n - len[q] - 1] != buf[n]; q = fail[q]);
        for(q = nxt[q][o]; len[q] > len[p] / 2; q = fail[q]);
        half[p] = q;
        nxt[cur][o] = p;
        if(!(len[p] & 1)) {
            f[p] = (cur ? f[cur] : len[p] / 2) + 1;
            if(!(len[q] & 1))
                f[p] = min(f[p], f[q] + len[p] / 2 - len[q] + 1);
            ans = min(ans, f[p] + slen - len[p]);
        }
    }
    cur = nxt[cur][o];
}
int main() {
    trans['A'] = 0;
    trans['G'] = 1;
    trans['C'] = 2;
    trans['T'] = 3;
    scanf("%d", &t);
    while(t--) {
        scanf("%s", str);
        ans = slen = strlen(str);
        init();
        for(int i = 0; i < slen; ++i)
            append(str[i]);
        printf("%d\n", ans);
    }
    return 0;
}