Manacher 模版

正文索引 [隐藏]

在 $O(n)$ 的时间复杂度内，求出字符串 str 内部的所有回文字符串。因为回文串数量级别可能到达 $O(n^2)$，所以这里求出的是具有代表性的回文串信息，即以 str 内任意位置为中心的最长回文串。

使用方法

  • 调用 build 函数，预处理字符串 s 的所有回文信息，函数返回 s 内最长的回文字符串长度，复杂度 $O(n)$。你需要先 bulid 才可以执行下列查询操作。（Python 代码这一步为类的构造函数，并不返回最长回文长度）
  • mid(x, true/false) 函数可以返回以某一个位置为中心的最长回文串，mid(x, true) 返回以字符串下标为 $x$ 的字母为中心的最长奇回文串长度，mid(x, false)，返回以字符串下标 $x,x+1$ 两个字母中间为中心的最长偶回文串长度，复杂度为 $O(1)$。
  • left(x) 函数可以返回从 $x$ 位置开始的最长回文串的长度，复杂度 $O(1)$。

字符串的下标均从 0 开始。

Left 数组

为了方便模板使用，额外维护了一个 Left 数组，为了计算以某一个字符为起点的最长回文子串的长度。

Left 数组的定义：在扩展之后的字符串上，以位置 $i$ 为起点的最长回文子串的中心在哪里。
Left 的计算有一点动态规划的意思：
C++ 代码的 21 行，我们先用得到的 ans 数组（每一个中心对应的最长回文子串中心到边界的距离）的值初始化 Left 数组，这样每一个最长回文子串的信息就对应左端点的 Left 数组中了。
C++ 代码 22 行，我们把回文信息扩展到所有的 Left 数组中。假设 $i<j$，且有 $Left[i]>Left[j]$，那么我们就可以将 $Left[j]$ 更新为 $Left[i]$，实际上相当于用了中心在 $Left[i]$ 的最长回文自子串的一个子串更新了 $Left[j]$。
查询的时候，我们知道了每一个起点的对应的最远回文中心，就可以将其相应的答案恢复出来。

C++ 代码

Python 代码

代码与 C++ 基本对应，故注释比较简单。

调用构造函数传入字符串 S 进行 Manacher 预处理，等同于 C++ 的 build 函数。注意，这步不返回 S 内最长回文串的长度，取而代之需要调用 max() 函数获得这个值，复杂度 $O(1)$。

left 与 mid 函数意义不变。

C++ 压缩代码

方便打印或网赛复制使用，压缩代码不是好习惯，大家看看就行……