document.write('最容易想到的方法为遍历字符串所有可能的子串(蛮力法)，判断其是否为回文字符串，然后找出最长
的回文子串。但是当字符串很长的时候，这种方法的效率是非常低下的，因此这种方法不可取。下
面介绍几种相对高效的方法。
方法一：动态规划法
在采用蛮力法找回文子串的时候有很多字符的比较是重复的，因此可以把前面比较的中间结果记
录下来供后面使用。这就是动态规划的基本思想。那么如何根据前面查找的结果判断后续的子串是
否为回文字符串呢?下面给出判断的公式，即动态规划的状态转移公式：
给定字符串“S0
S1
S2…Sn”，假设P(i,j)=1表示“SiSi+1…Sj”是回文字符串；P(i,j)=0则表
示“SiSi+1…Sj”不是回文字符串。那么：
P(i,1)=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)。
根据这几个公式，实现代码如下：
class Test:
def __new__(seif):
self.startIndex=None
self,lens=None
def getStartIndex(self): return self.startIndex
def getLen(self): return self.lens
"""
方法功能: 找出字符串中最长的回文予串
输入参数: str为字符串,startIndex与len为找到的回文字符串的起始位置与长度
"""
def getLongestPalindrome(self,strs):
if strs==None:
return
n=len(strs)#字符串长度
if n＜1:
return
self.startIndex=0
self.lens=1
#申请额外的存储空间记录查找的历史信息
historyRecord=[([None]*n) for i in range(n)]
i=0
while i＜n:
j=0
while j＜n:
historyRecord[i][j]=0
j+=1
i+=1
#初始化长度为1的回文字符串信息
i=0
while i＜n:
historyRecord[i][i]=1
i+=1
#初始化长度为2的回文字符串信息
i=0
while i＜n-1:
if List(strs)[i]==list(strs)[i+1]:
historyRecord[i][i+1]=1
self.startIndex=i
self.lens=2
i+=1
#查找从长度为3开始的回文字符串
pLen=3
while pLen＜=n:
i=0
while i＜n-pLen+1:
j=i+pLen-1
if list(strs)[i]==list(strs)[j] and historyRecord[i+1][j-1]==1:
historyRecord[il[j]=1
self.startIndex=i
self.lens=pLen
i+=1
pLen+=1
if __name__=="__main__":
strs="abcdefgfedxyz"
t=Test()
t.getLongestPalindrome(strs)
if t.getStartIndex()!=-1 and t.getLen()!=-1:
print "最长的回文字串为: ",
i=t.getStartIndex()
while i＜t.getStartIndex()+t.getLen():
print list(strs)[i],
i+=1
else:
print "查找失败"
程序的运行结果为：
最一长的回文子串为：defgfed
算法性能分析：
这种方法的时间复杂度为O(n2
)，空间复杂度也为O(n2
)。
此外，还有另外一种动态规划的方法来实现最长回文字符串的查找。主要思路为：对于给定的字
符串str1，求出对其进行逆序的字符串str2，然后str1与str2的最长公共子串就是str1的最长回文子
串。
方法二：中心扩展法
判断一个字符串是否为回文字符串最简单的方法为：从字符串最中间的字符开始向两边扩展，通
过比较左右两边字符是否相等就可以确定这个字符串是否为回文字符串。这种方法对于字符串长度
为奇数和偶数的情况需要分别对待。例如：对于字符串“aba”，就可以从最中间的位置b开始向两
边扩展；但是对于字符串“baab”，就需要从中间的两个字母开始分别向左右两边扩展。
基于回文字符串的这个特点，可以设计这样一个方法来找回文字符串：对于字符串中的每个字符
Ci，向两边扩展，找出以这个字符为中心的回文子串的长度。由于上面介绍的回文字符串长度的奇
偶性，这里需要分两种情况：(1)以Ci为中心向两边扩展；(2)以Ci和Ci+1为中心向两边扩展。实现代
码如下：
class Test:
def __init__(self):
self.startIndex=None
self.lens=None
def getStartIndex(self): return self.startIndex
def getLen(self): return self.lens
#对字符串str, 以c1和c2为中心向两侧扩展寻找回文子串
def expandBothSide(self,strs,c1,c2):
n=len(strs)
while c1＞=0 and c2＜n and list(strs)[c1]==list(strs)[c2]:
c1-=1
c2+=1
tmpStartIndex=c1+1
tmpLen=c2-c1-1
if tmpLen＞self.lens:
self.lens=tmpLen
self.startIndex=tmpStartIndex
#方法功能: 找出字符串最长的回文子串
def getLongestPalindrome(self,strs):
if strs==None:
return
n=len(strs)
if(n＜1):
return
i=0
while i＜n-1:
#找回文字符串长度为奇数的情况 (从第i个字符向两边扩展)
self.expandBothSide(strs,i,i)
#找回文字符串长度为偶数的情况(从第i和i+1两个字符向两边扩展)
self.expandBothSide(strs,i,i+1)
i+=1
if __name__=="__main__":
strs="abcdefgfedxyz"
t=Test()
t.getLongestPalindrome(strs)
if t.getStartIndex()!=-1 and t.getLen()!=-1:
print "最长的回文字串为:",
i=t.getStartIndex()
while i＜t.getStartIndex()+t.getLen():
print list(strs)[i],
i+=1
else:
print "查找失败"
算法性能分析：
这种方法的时间复杂度为O(n2
)，空间复杂度为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*idi]，在此基础上继续向两边扩展，求出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]=MN(P[2*id-i],P[id]-i)，然后在此基础上向两边继续扩展寻找最长的回文子串，根据这个思路
的实现代码如下：
class Test:
def __init__(self):
self.center=None
self.palindromeLen=None
def getCenter(self):return selfcenter
def getLen(self):return selfpalindromeLen
def mins(self,a,b):
return bif a＞b else a
"""
方法功能: 找出字符串最长的回文子串
输入参数: str为字符串, center为回文字符的中心字符, len表示回文字符串长度
如果长度为偶数, 那么表示中间偏左边的那个字符的位置
"""
def Manacher(self,strs):
lens=len(strs) #字符串长度
newLen=2*lens+1
s=[None]*newLen#插入分隔符后的字符串
p=[None]*newLen
id=0 #id表示以第id个字符为中心的回文字符串最右端的下标值最大
i=0
while i＜newLen:
#构造填充字符串
s[i]=\'*\'
p[i]=0
i+=1
i=0
while i＜lens:
s[(i+1)*2]=list(strs)
i+=1
self.center=-1
self.palindromeLen=-1
#求解p数组
i=1
while i＜newLen:
if id+p[id]＞i: #图中(1),(2),(3)三种情况
p[i]=self.mins(id+p[id]-i, p[2*id-i])
else: #对应图中第(4)种情况
p[i]=1
#然后接着向左右两边扩展求最长的回文予串
while i+p[i]＜newLen and i-p[i]＞0 and s[i-p[i]]==s[i+p[i]]:
p[i]+=1
#当前求出的回文字符串最右端的下标更大
if i+p[i]＞id+p[id]:
id=i
#当前求出的回文字符串更长
if p[i]-1＞self.palindromeLen:
self.center=(i+1)/2-1
self.palindromeLen=p[i]-1 #更新最长回文子串的长度
i+=1
if __name__=="__main__":
strs="abcbax"
t=Test()
t.Manacher(strs)
center=t.getCenter()
palindromeLen=t.getLen()
if center!=-1 and palindromeLen!=-1:
print "最长的回文子串为:",
#回文字符串长度为奇数
if palindromeLen%2==1:
i=center-palindromeLen/2
while i＜=center+palindromeLen/2:
print list(strs)[i],
i+=1
#回文字符串长度为偶数
else:
i=center-palindromeLen/2
while i＜center+palindromeLen/2:
print list(strs)[i],
i+=1
else:
print "查找失败"
程序的运行结果为：
最长的回文子串为：abcba
算法性能分析：
这种方法的时间复杂度和空间复杂度都为O(N)。
');
![\"360截图20190814161158540.jpg\"](\"http://www.alatiku.com/d/file/shiti/4f937869477aa2e716475b48c47878d2.jpg\")