在介绍 Manacher 算法之前,首先介绍一下什么是回文串,所谓回文串,简单来说就是正着读和反着读都是一样的字符串,比如 abba,noon 等等,一个字符串的最长回文子串即为这个字符串的子串中,是回文串的最长的那个。

计算字符串的最长回文字串最简单的算法就是枚举该字符串的每一个子串,并且判断这个子串是否为回文串,这个算法的时间复杂度为 O(n3)O(n^3) 的,显然无法令人满意,稍微优化的一个算法是枚举回文串的中点(把每一个字符当做中心,向两边延伸),这里要分为两种情况,一种是回文串长度是奇数的情况,另一种是回文串长度是偶数的情况,枚举中点再判断是否是回文串,这样能把算法的时间复杂度降为O(n2)O(n^2),但是当 n 比较大的时候仍然无法令人满意,Manacher 算法可以在线性时间复杂度内求出一个字符串的最长回文字串,达到了理论上的下界。

1. Manacher 算法原理与实现

首先,Manacher 算法提供了一种巧妙地办法,将长度为奇数的回文串和长度为偶数的回文串一起考虑,具体做法是,在原字符串的每个相邻两个字符中间插入一个分隔符,同时在首尾也要添加一个分隔符,分隔符的要求是不在原串中出现,一般情况下可以用#号。下面举一个例子:

-w500

1.1 Len数组简介与性质

Manacher算法用一个辅助数组Len[i]表示以字符T[i]为中心的最长回文字串的最右字符到T[i]的长度,比如以T[i]为中心的最长回文字串是T[l,r],那么Len[i]=r-i+1。

对于上面的例子,可以得出Len[i]数组为:

-w450

Len数组有一个性质,那就是Len[i]-1就是该回文子串在原字符串S中的长度,至于证明,首先在转换得到的字符串T中,所有的回文字串的长度都为奇数,那么对于以T[i]为中心的最长回文字串,其长度就为2Len[i]12*Len[i]-1,经过观察可知,T中所有的回文子串,其中分隔符的数量一定比其他字符的数量多1,也就是有Len[i]个分隔符,剩下Len[i]-1个字符来自原字符串,所以该回文串在原字符串中的长度就为Len[i]-1。

有了这个性质,那么原问题就转化为求所有的Len[i]。下面介绍如何在线性时间复杂度内求出所有的Len。

1.2 Len数组的计算

首先从左往右依次计算Len[i],当计算Len[i]时,Len[j] (0<=j<i)(0<=j<i) 已经计算完毕。设 P 为之前计算中所有最长回文子串中,所能到达最右一个字符的位置。并且设 P 对应的回文串的对称轴所在的位置,记为 po。显然,我们当前要访问的 i,是在po的右边。但i 与 位置P,有两种情况:

第一种情况:i<=P

那么找到 i 相对于 po 的对称位置,设为 j,那么如果Len[j]<P-i,如下图:

-w450

那么说明以 j 为中心的回文串一定在以po为中心的回文串的内部,且j和i关于位置 po 对称,由回文串的定义可知,一个回文串反过来还是一个回文串,所以以 i 为中心的回文串的长度至少和以 j 为中心的回文串一样,即Len[i]>=Len[j]。因为Len[j]<P-i,所以说i+Len[j]<P。由对称性可知Len[i]=Len[j]。( to check)

如果Len[j]>=P-i,由对称性,说明以i为中心的回文串可能会延伸到P之外,而大于P的部分我们还没有进行匹配,所以要从P+1位置开始一个一个进行匹配,直到发生失配,从而更新P和对应的po以及Len[i]。

-w450

第二种情况: i>P

如果 i 比 P 还要大,说明对于中点为 i 的回文串还一点都没有匹配,这个时候,就只能老老实实地一个一个匹配了,匹配完成后要更新 P 的位置和对应的 po 以及Len[i]。

-w450

参考:

  1. https://segmentfault.com/a/1190000003914228
  2. https://blog.csdn.net/dyx404514/article/details/42061017