【正确答案】最容易想到的方法为遍历字符串所有可能的子串(蛮力法)，判断其是否为回文字符串，然后找出最长的回文子串。但是当字符串很长的时候，这种方法的效率是非常低下的，因此这种方法不可取。下面介绍几种相对高效的方法。
   方法一：动态规划法
   在采用蛮力法找回文子串的时候有很多字符的比较是重复的，因此可以把前面比较的中间结果记录下来供后面使用。这就是动态规划的基本思想。那么如何根据前面查找的结果判断后续的子串是否为回文字符串呢?下面给出判断的公式，即动态规划的状态转移公式：
   给定字符串“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,1)=1
   如果S_i==S_i+1：那么P(i,i+1)=1，否则P(i,i+1)=0。
   如果S_i+1==S_j+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(n²)，空间复杂度也为O(n²)。
   此外，还有另外一种动态规划的方法来实现最长回文字符串的查找。主要思路为：对于给定的字符串str1，求出对其进行逆序的字符串str2，然后str1与str2的最长公共子串就是str1的最长回文子串。
   方法二：中心扩展法
   判断一个字符串是否为回文字符串最简单的方法为：从字符串最中间的字符开始向两边扩展，通过比较左右两边字符是否相等就可以确定这个字符串是否为回文字符串。这种方法对于字符串长度为奇数和偶数的情况需要分别对待。例如：对于字符串“aba”，就可以从最中间的位置b开始向两边扩展；但是对于字符串“baab”，就需要从中间的两个字母开始分别向左右两边扩展。
   基于回文字符串的这个特点，可以设计这样一个方法来找回文字符串：对于字符串中的每个字符Ci，向两边扩展，找出以这个字符为中心的回文子串的长度。由于上面介绍的回文字符串长度的奇偶性，这里需要分两种情况：(1)以C_i为中心向两边扩展；(2)以C_i和C_i+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(n²)，空间复杂度为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]的值呢?如下图所示可以分为四种情况来讨论：