python最长回文串算法

这篇文章主要为大家详细介绍了python最长回文串算法的实践，具有一定的参考价值，感兴趣的小伙伴们可以参考一下

由于对称性，可得i+i" = 2*j。因此第一种情况下，f[i]>=f[2*j-i]；第二种情况下，f[i]>=f[j]+2*j-2*i。

综上1,2，可得f[i]>=min(f[2*j-i],f[j]+2*j-2*i)。由于i右边存在未遍历的字符，因此在此基础上，继续向两边扩展，直到找到最长的回文子串。

若i依然在j+f[j]/2后面，则表示i没有被前面的字符的影响，只能逐一的向两边扩展。

这个算法由于只需遍历一遍字符串，扩展的次数也是有限的，所以时间复杂度可以达到O（N）。

下面是Pthon3的程序，为了检测算法的效率，依然提供最初的暴力枚举算法作为最坏算法的参照。

python代码：

#求最长回文串类 
class LPS:           
  #初始化，需要提供一个字符串  
  def __init__(self,string): 
    self.string = string 
    self.lens = len(self.string) 
   
  #暴力枚举：作为算法效率参照 
  def brute_force(self): 
    maxcount = 0 
    for j in range(self.lens):            
      for k in range(j,self.lens): 
        count = 0 
        l,m = j,k 
        while m>=l: 
          if self.string[l]==self.string[m]: 
            l,m = l+1,m-1 
          else: 
            break 
        if m<l: 
          count = k-j+1 
        if count>maxcount : 
          maxcount = count 
    return maxcount 
   
  #优化版：枚举子串中心 
  def brute_force_opti(self): 
    maxcount = 0 
    if self.lens == 1:               #只有一个字符直接返回1 
      return 1 
    for j in range(self.lens-1):          #枚举中心 
      count,u = 1,j  
      #对于奇数子串，直接扩展 
      for k in range(1,j+1):           #两边扩展 
        l,m = u+k,j-k 
        if (m>=0)&(l<self.lens): 
          if(self.string[l]==self.string[m]): 
            count += 2 
          else: 
            break 
      if count>maxcount :             #更新回文子串最长长度 
        maxcount = count 
      if self.string[j]==self.string[j+1]:    #处理偶数子串，将两个相邻相同元素作为整体 
        u,count= j+1,2 
      for k in range(1,j+1):           #两边扩展 
        l,m = u+k,j-k 
        if (m>=0)&(l<self.lens): 
          if(self.string[l]==self.string[m]): 
            count += 2 
          else: 
            break 
      if count>maxcount :             #更新回文子串最长长度 
        maxcount = count 
    return maxcount 
     
  #manacher算法 
  def manacher(self): 
    s = '#'+'#'.join(self.string)+'#'        #字符串处理，用特殊字符隔离字符串，方便处理偶数子串 
    lens = len(s) 
    f = []                     #辅助列表：f[i]表示i作中心的最长回文子串的长度 
    maxj = 0                    #记录对i右边影响最大的字符位置j 
    maxl = 0                    #记录j影响范围的右边界 
    maxd = 0                    #记录最长的回文子串长度 
    for i in range(lens):              #遍历字符串 
      if maxl>i:                  
        count = min(maxl-i,int(f[2*maxj-i]/2)+1)#这里为了方便后续计算使用count，其表示当前字符到其影响范围的右边界的距离 
      else :                    
        count = 1 
      while i-count>=0 and i+count<lens and s[i-count]==s[i+count]:#两边扩展 
        count +=1 
      if(i-1+count)>maxl:             #更新影响范围最大的字符j及其右边界 
          maxl,maxj = i-1+count,i                             
      f.append(count*2-1) 
      maxd = max(maxd,f[i])            #更新回文子串最长长度 
    return int((maxd+1)/2)-1            #去除特殊字符

通过上面的程序，使用字符串为长度1000的纯‘a'字符串作为样例，经过测试：

暴力枚举：49.719844s

中心枚举：0.334019s

manacher：0.008000s

由此可见，长度为1000时，暴力枚举的耗时已经无法忍受了，而相比而言，中心枚举在效率上已经有很大幅度的提升，最优的manacher耗时则为更短。