题解

思路

设选择的前缀长度为 $i$，后缀长度为 $j$，并令 $t=\min(i,j)$。拼接串最外侧的 $2t$ 个字符能够匹配，当且仅当 $S$ 的前 $t$ 个字符等于 $S$ 的后 $t$ 个字符的逆序。

去掉这 $2t$ 个外层字符后，只会在较长的一侧剩下一段。若前缀较长，剩余段是从位置 $t$ 开始的回文子串；若后缀较长，剩余段在原串中以位置 $n-t-1$ 结束，等价于在反串中从位置 $t$ 开始的回文子串。

做法

先求原串与反串的最长公共前缀长度 $L$，于是只需枚举 $0\le t\le L$。

对于小规模，可以枚举前缀和后缀长度并直接检查拼接结果。中等规模可以用回文动态规划预处理每个位置开始的最长回文子串。

满分做法分别对原串和反串运行 Manacher。每个奇回文中心会对一段连续起点贡献长度为一次函数的候选，每个偶回文中心也同理。按起点从左到右扫描，用优先队列维护当前仍覆盖该起点、且右端点最远的回文中心，即可得到每个位置开始的最长回文子串长度。

最后对每个 $t$ 计算

$$2t+\max(\text{start}_S[t],\text{start}_{\operatorname{rev}(S)}[t]),$$

取最大值。

正确性说明

任意合法拼接串的两侧各取较短部分的全部字符，恰好形成前缀与逆序后缀的逐字符匹配，因此其长度不超过某个合法 $t$ 的外层 $2t$ 加上一段相邻回文。反之，任意满足外层匹配的 $t$，再接上原串或反串中从 $t$ 开始的回文段，都能构成一个合法的前缀与后缀拼接回文。两方面合并，枚举式恰好覆盖全部合法方案。

复杂度

Manacher 与最长公共前缀为 $O(n)$，区间扫描为 $O(n\log n)$，空间复杂度为 $O(n)$。