ABB 题解

思路

设最终在末尾添加了 $k$ 个字符。若整个结果是回文串，那么新加入的部分必须依次等于原串前 $k$ 个字符的逆序。删去这两段互相对应的字符后，原串剩余的后缀必须自身是回文串。

反过来，若从位置 $k+1$ 开始的后缀是回文串，只需在末尾补上原串前 $k$ 个字符的逆序，得到的整个字符串一定是回文串。

因此，答案等于

其中 $L$ 是原串最长回文后缀的长度。

子任务 1：直接检查后缀

依次枚举后缀的起点，并用双指针判断该后缀是否为回文串。第一个满足条件的起点对应最长回文后缀，也就是答案。

每次检查需要 $O(N)$ 时间，共有 $O(N)$ 个后缀，因此时间复杂度为 $O(N^2)$，额外空间复杂度为 $O(1)$。该方法适用于 $N\le 3000$。

做法

满分算法：前缀函数

记 $R$ 为 $S$ 的逆序串，构造

其中分隔符不在小写字母表中。

计算 $T$ 的前缀函数。最后一个位置的前缀函数值记为 $L$，它表示 $T$ 的最长前缀与后缀的公共长度。由于分隔符隔开了两部分，这个公共长度不会跨过分隔符；它恰好比较 $R$ 的长度为 $L$ 的前缀与 $S$ 的长度为 $L$ 的后缀。

$R$ 的这一前缀正是 $S$ 对应后缀的逆序。因此两者相等，当且仅当该后缀是回文串。前缀函数取最大的可行长度，所以得到的正是最长回文后缀长度。

最终输出 $N-L$。

正确性证明

引理 1：若在 $S$ 末尾添加 $k$ 个字符后得到回文串，则 $S$ 去掉前 $k$ 个字符后的后缀是回文串。

证明：最终回文串的前 $k$ 个字符与后 $k$ 个字符互为逆序。删去这两段后，中间剩余部分仍为回文串，而该部分正是所述后缀。

引理 2：若 $S$ 去掉前 $k$ 个字符后的后缀是回文串，则可以只添加 $k$ 个字符使整个字符串成为回文串。

证明：在末尾添加 $S$ 前 $k$ 个字符的逆序。新增部分与原串前缀互相对应，中间后缀本身回文，所以整个字符串回文。

引理 3：构造串 $T$ 的最后一个前缀函数值等于 $S$ 的最长回文后缀长度。

证明：长度为 $x$ 的匹配表示 $R$ 的长度为 $x$ 的前缀等于 $S$ 的长度为 $x$ 的后缀。前者是后者的逆序，因此匹配当且仅当该后缀回文。前缀函数选择最大的匹配长度，结论成立。

定理：算法输出的数值是使 $S$ 成为回文串所需添加字符数的最小值。

证明：由引理 3，算法找到最长回文后缀长度 $L$。由引理 2，添加 $N-L$ 个字符一定可行；若存在更少的添加量，引理 1 将导出一个长度大于 $L$ 的回文后缀，与 $L$ 的最大性矛盾。因此答案最优。

复杂度分析

构造逆序串和计算前缀函数均为线性过程。时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。

独立验证

数据生成时还使用 Manacher 算法独立求出所有奇回文和偶回文半径，选取右端点为 $N-1$ 的最长回文段。该实现与前缀函数方法的数据结构和推导路径不同，可用于交叉核对答案。