题解

思路

先比较字符串首尾字符。只要两端相同，它们就可以同时放入答案的开头和结尾，而且不会妨碍中间部分保持回文。设最多能这样保留 $k$ 对字符，剩余中段记为 $m$。

中段不能再同时取首尾字符。此时任何合法答案在中段中只能选择一个回文前缀，或选择一个回文后缀；否则同时选择中段两端的非空部分会要求它们的首尾字符相同，与 $k$ 的最大性矛盾。因此只需比较 $m$ 的最长回文前缀和最长回文后缀。

做法

对每个字符串执行以下步骤：

1. 从两端向中间扫描，求出最大的 $k$，使前 $k$ 个字符与后 $k$ 个字符逆序对应相等。
2. 取中段 $m=s[k\ldots |s|-k-1]$。
3. 用 Manacher 算法求出中段所有奇回文和偶回文区间，据此得到最长回文前缀长度与最长回文后缀长度。
4. 选择较长者，拼接外层前缀、所选中段回文和外层后缀。

若整个字符串已经被外层匹配覆盖，直接输出原串。

正确性证明

由 $k$ 的定义，外层前缀与外层后缀互为逆序，二者同时加入任何回文中段后仍构成回文，因此保留全部 $k$ 对字符不会降低可行答案长度。

若中段 $m$ 非空，则它的首字符和尾字符不同。合法答案在中段中由某个前缀与某个后缀拼接而成。若两部分都非空，所得回文的首字符和尾字符必须相同，但它们分别是 $m$ 的首字符和尾字符，产生矛盾。因此最优答案在中段中必为回文前缀或回文后缀。算法枚举了这两类中的最长者，故其中段选择最优；再加上必然可以全部保留的外层 $2k$ 个字符，得到全局最长合法答案。

复杂度

设所有输入字符串长度之和为 $N$。Manacher 扫描和外层匹配均为线性，时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。