感觉自己之前学的时候没学清楚,于是重新整理了一遍.
本文主要整理自 2014年集训队论文 《浅谈回文子串问题 徐毅》.
回文半径
以字符串第 $i$ 个位置为中心的回文子串长度的一半,称为该字符串第 $i$ 位的回文半径,记作 $R(i)$ .
预处理
处理回文子串问题时,为了方便,经常将原字符串加入特殊字符,避免奇偶讨论与边界问题.
如: "abbabcba" -> "$#a#b#b#a#b#c#b#a#@"
对新字符串求出每个位置的回文半径,就对应了原串中以字符为中心的奇回文串和以空隙为中心的偶回文串.
$Manacher$ 算法
又称马拉车算法.
可以以 $O(n)$ 的时间复杂度求解长度为 $n$ 的字符串每个位置的回文半径.
首先执行上文的预处理,再依次计算位置 $1\sim n$ 的回文半径.
记 $mx$ 表示已经计算出的回文半径覆盖到的最右边界,即 $\max k+R(k)-1$ .
记 $p$ 为对应中心的位置,即使得 $k+R(k)-1$ 取得最大值的 $k$ .
枚举 $i$ ,计算 $R(i)$ 时,考虑暴力匹配的过程,就是从 $i$ 不断向外拓展,也就是从 $1$ 开始枚举 $R(i)$ ,直到不能拓展.
$Manacher$ 算法就是通过记录的 $mx,p$ ,来给 $R(i)$ 确定一个下界,这样枚举 $R(i)$ 时只用从下界开始枚举.
记 $j=2p-i$ ,即 $i$ 关于 $p$ 的对称位置.分以下 $3$ 种情况进行讨论:
情况一:
$mx<i$ ,只能确定 $R(i)\ge 1$.
情况二:
$mx-i>R(j)$ ,即以第 $j$ 位为中心的回文子串包含于以第 $p$ 位为中心的回文子串.
由于 $i$ 和 $j$ 关于 $p$ 对称,以第 $i$ 位为中心的回文子串必然也包含于以第 $p$ 位为中心的回文子串,故有 $R(i)=R(j)$ .
情况三:
$mx-i\le R(j)$ ,此时以第 $j$ 位为中心的回文子串不一定包含于以第 $p$ 位为中心的回文子串.
但因为 $i$ 与 $j$ 关于 $p$ 对称,所以以 $i$ 为中心向右至少能拓展到 $mx$ 的位置,即 $R(i)\ge mx-i+1$ .
在情况一与三中,确定下界后,再从下界开始枚举 $R(i)$ ,继续拓展,即暴力向外匹配.
不难验证,每次暴力向外匹配都会使得 $mx$ 增大,而 $mx$ 最多增大 $n$ 次,所以算法时间复杂度为 $O(n)$ .
从跳 $mx$ 的过程中也可以得到关于回文子串的两条比较重要的性质:
性质一:
一个长度为 $n$ 的字符串含有的本质不同的回文子串只有 $O(n)$ 个.
这是因为只有 $mx$ 增大时,才会产生本质不同的回文子串,否则一定存在对称的回文子串,而 $mx$ 增大不会超过 $n$ 次.
于是可以在算法执行过程中将所有本质不同的回文子串的位置给处理出来,在 $mx$ 增大时进行记录即可.
性质二:
一个长度为 $n$ 的字符串的回文性质可以用 $O(n)$ 个相等与不等关系表示.
定义一个字符串的回文性质为所有回文子串出现位置的集合.
即,若串 $S$ 与串 $T$ 具有相同的回文性质,则 $S(i,\dots j)$ 为回文串,当且仅当 $T(i,\dots,j)$ 为回文串.
而一个串 $S$ 的回文性质可以用一些相等和不等关系表示.对于以第 $i$ 位为中心的回文子串,显然有 $0\le k<R(i),S[i-k]=S[i+k]$ ,以及 $S[i-R(i)]\not=S[i+R(i)]$ ,这就是一些相等与不等关系.
只有当 $mx$ 增大时,才会产生新的相等关系,否则一定存在对称的相等关系,相等关系数量是 $O(n)$ 的.
而每个位置作为回文中心只会产生一个不等关系,不等关系数量也是 $O(n)$ 的.
所以可以只用 $O(n)$ 个相等和不等关系表示回文性质.