求字符串最长回文子串算法：Kotlin实现

【出自BD笔试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

回文字符串是指一个字符串从左到右与从右到左遍历得到的序列是相同的。例如“abcba”就是回文字符串，而“abcab”则不是回文字符串。

分析与解答：

最容易想到的方法为遍历字符串所有可能的子串（蛮力法），判断其是否为回文字符串，然后找出最长的回文子串。但是当字符串很长的时候，这种方法的效率是非常低的，因此这种方法不可取。下面介绍几种相对高效的方法。

方法一：动态规划法

在采用蛮力法找回文子串的时候有很多字符的比较是重复的，因此，可以把前面比较的中间结果记录下来供后面使用。这就是动态规划的基本思想。那么如何根据前面查找的结果，判断后续的子串是否为回文字符串呢？下面给出判断的公式，即动态规划的状态转移公式。

给定字符串“S₀S₁S₂…S_n”，假设P（i，j）=1表示“S_iS_i+1…S_j”是回文字符串；P（i，j）=0则表示“S_iS_i+1…S_j”不是回文字符串。那么：

P（i，i）=1

如果Si==Si+1，则P（i，i+1）=1，否则P（i，i+1）=0。

如果Si+1==Sj+1，则P（i+1，j+1）=P（i，j）。

根据这几个公式，实现代码如下：

程序的运行结果如下：

最长的回文子串为：defgfed

算法性能分析：

这种方法的时间复杂度为O（n^2），空间复杂度也为O（n^2）。

此外，还有另外一种动态规划的方法来实现最长回文字符串的查找。主要思路是：对于给定的字符串str1，求出对其进行逆序的字符串str2，然后str1与str2的最长公共子串就是str1的最长回文子串。

方法二：中心扩展法(www.xing528.com)

判断一个字符串是否为回文字符串最简单的方法是：从字符串最中间的字符开始向两边扩展，通过比较左右两边字符是否相等就可以确定这个字符串是否为回文字符串。这种方法对于字符串长度为奇数和偶数的情况需要分别对待。例如：对于字符串“aba”，就可以从最中间的位置b开始向两边扩展；但是对于字符串“baab”，就需要从中间的两个字母开始分别向左右两边扩展。

基于回文字符串的这个特点，可以设计这样一个方法来找回文字符串：对于字符串中的每个字符C_i，向两边扩展，找出以这个字符为中心的回文子串的长度。由于上面介绍的回文字符串长度的奇偶性，这里需要分两种情况：（1）以C_i为中心向两边扩展；（2）以C_i和C_i+1为中心向两边扩展。实现代码如下：

算法性能分析：

这种方法的时间复杂度为O（n^2），空间复杂度为O（1）。

方法三：Manacher算法

方法二需要根据字符串的长度分偶数与奇数两种不同情况单独处理，Manacher算法可以通过向相邻字符中插入一个分隔符，把回文字符串的长度都变为奇数，从而可以对这两种情况统一处理。例如：对字符串“aba”插入分隔符后变为“*a*b*a*”，回文字符串的长度还是奇数。对字符串“aa”插入分隔符后变为“*a*a*”，回文字符串长度也是奇数。因此，采用这种方法后可以对这两种情况统一进行处理。

Manacher算法的主要思路是：首先在字符串中相邻的字符中插入分割字符，字符串的首尾也插入分割字符（字符串中不存在的字符，本例以字符*为例作为分割字符）。接着用另外的一个辅助数组P来记录以每个字符为中心对应的回文字符串的信息。P[i]记录了以字符串第i个字符为中心的回文字符串的半径（包含这个字符），以P[i]为中心的回文字符串的长度为2*P[i]-1。P[i]-1就是这个回文字符串在原来字符串中的长度。例如：“*a*b*a*”对应的辅助数组P为{1，2，1，4，1，2，1}，最大值为P[3]=4，那么原回文字符串的长度则为4-1=3。

那么如何来计算P[i]的值呢，如下图所示可以分为四种情况来讨论：

假设在计算P[i]的时候，在已经求出的P[id]（id＜i）中，找出使得id+p[id]的值为最大的id，即找出这些回文字符串的尾字符下标最大的回文字符的中心的下标id。

（1）i没有落到P[id]对应的回文字符串中（如上图（1））。此时因为没有参考的值，所以只能把字符串第i个字符作为中心，向两边扩展来求P[i]的值。

（2）i落到了P[id]对应的回文字符串中。此时可以把id当作对称点，找出i对称的位置2*id-i，如果P[2*id-i]对应的回文字符的左半部分有一部分落在P[id]内，另外一部分落在P[id]外（如上图（2）），那么P[i]=id+P[id]-i，也就是P[i]的值等于P[id]与P[2*id-i]重叠部分的长度。需要注意的是，P[i]不可能比id+P[id]-i更大，证明过程如下：假设P[i]＞id+P[id]-i，以i为中心的回文字符串可以延长a、b两部分（延长的长度足够小，使得P[i]＜P[2*id-i]），如上图（2）所示：根据回文字符串的特性可以得出：a=b，找出a与b以id为对称点的子串d和c。由于d和c落在了P[2*id-i]内，因此，c=d，又因为b和c落在了P[id]内，因此，b=c，所以，可以得到a=d，这与已经求出的P[id]矛盾，因此，p[id]的值不可能更大。

（3）i落到了P[id]对应的回文字符串中，把id当作对称点，找出i对称的位置2*id-i，如果P[2*id-i]对应的回文字符的左半部分与P[id]对应的回文字符的左半部分完全重叠，则p[i]的最小值为P[2*id-i]，在此基础上继续向两边扩展，求出P[i]的值。

（4）i落到了P[id]对应的回文字符串中，把id当作对称点，找出i对称的位置2*id-i，如果P[2*id-i]对应的回文字符的左半部分完全落在了P[id]对应的回文字符的左半部分，则p[i]=P[2*id-i]。

根据以上四种情况可以得出结论：P[i]＞=MIN（P[2*id-i]，P[id]-i）。在计算时可以先求出P[i]=MIN（P[2*id-i]，P[id]-i），然后在此基础上向两边继续扩展寻找最长的回文子串，根据这个思路的实现代码如下：

程序的运行结果如下：

最长的回文子串为：abcba

算法性能分析：

这种方法的时间复杂度和空间复杂度都为O（N）。