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)

leftmid 函数意义不变。

C++ 压缩代码

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