解题思路

思路

回文子串由中心唯一确定。直接从每个字符或每两个相邻字符之间向两侧扩展，可以求出所有奇长和偶长回文，但在重复字符串上会重复比较大量区间。

Manacher 算法利用已知最右回文内的对称信息，为新中心提供一个不需要重新比较的初始半径。只有超过当前最右边界的部分才会进行新的字符比较。

做法

子任务 1

枚举每一个奇回文中心和偶回文中心，不断比较左右对称字符，统计最大长度。

满分做法

分别计算两个半径数组：

• $d_1[i]$ 表示以 $i$ 为中心的最长奇回文半径，对应长度为 $2d_1[i]-1$；
• $d_2[i]$ 表示以 $i-1$ 和 $i$ 之间为中心的最长偶回文半径，对应长度为 $2d_2[i]$。

计算某个位置时，维护当前右端点最大的已知回文区间 $[l,r]$。若新中心在区间内，它的初始半径可由对称位置的半径与右边界共同限制；然后仅继续扩展尚未比较的部分。如果得到更远的右端点，就更新 $[l,r]$。

正确性说明

对于已知回文区间内的中心，其对称位置上已经验证过的字符对在对称后仍然相等，因此可安全复用；初始半径不超过右边界，所以不会假定区间外的字符相等。随后的逐字符扩展恰好验证了该中心剩余的最大可能范围。因而每个 $d_1[i]$ 和 $d_2[i]$ 都是对应中心的真实最大半径，取所有对应长度的最大值即为答案。

复杂度

子任务 1 的时间复杂度为 $O(n^2)$，额外空间复杂度为 $O(1)$。Manacher 算法中最右边界只会单调向右移动，因此时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。