Manacher

的时间复杂度内求出一个字符串的任意位置为中心的最大字符串。

首先为了统一奇字符串和偶字符串，

我们在字符串每个位置加入一个特殊字符 # ，

在字符串开头加入特殊字符 $ 。

然后所有回文串就都是寄回文串了。

记 为以 为中心的回文串的最长半径，

那么 就是原串长度。

然后在暴力拓展的基础上，记录当前回文串可以延展到的最右意义位置 （注意，是 ） 和其中心

每当访问一个新位置 ，我们先提前确定一部分 。

如果 , 那么由回文串的对称性， 。

所以我们可以先另 ，剩下的部分暴力拓展。

再用 更新 。

例题：

吉哥系列故事——完美队形II

先用 求出每个中心的最长回文串，再求出每个点结束、开始的最长不下降、不上升子串的最长长度，两者取最小值即可。

#2452. 「POI2010」反对称 Antisymmetry

求子串中满足任意首位相加等于 的有多少。

魔改一下马拉车即可。因为都是偶串，所以只扩展#。

然后把判断条件改为相加等于一，并跳过 #。

为什么这样是对的？因为反对称， 与 的扩展过程完全相同，只不过访问到的 相反。