python最長回文串演算法

這篇文章主要為大家詳細介紹了python最長回文串演算法的實踐，具有一定的參考價值，有興趣的小夥伴們可以參考一下

給定一個字串，要求在這個字串中找到符合回文性質的最長子字串。所謂回文性是指諸如 “aba”,"ababa","abba"這類的字串，當然單個字元以及兩個相鄰相同字元也滿足回文性質。

看到這個問題，最先想到的解決方法自然是暴力枚舉，透過枚舉字串所有字符串的起點，逐一判斷滿足回文性的子串，記錄長度並更新最長長度。顯然這種演算法的時間複雜度是很高的，最壞情況可以達到O（N*N）。所以呢，這裡提出一個優化的方案，透過列舉字串子字串的中心而不是起點，向兩邊同時擴散，依然是逐一判斷子字串的回文性。這種最佳化演算法比之前的演算法在最壞的情況下（即只有一種字元的字串）效率會有很大程度的上升。

由上述的最佳化方案，我們知道了枚舉中心要比枚舉起點效率要好，然而這並不是最優的演算法。由於枚舉中心的演算法同時影響的是中心兩邊的字符，所以我們可以透過枚舉中心的左邊字符作為中心的子串的回文性判斷枚舉中心右邊的字符作為中心得子串的回文性，這就是manacher演算法。

manacher演算法思想非常巧妙，首先遍歷字串，假設i 為枚舉中心，則j (jaa007f7ceb1a6053b47842d425acedd3=f[i']

2 . i 關於j 對稱的字符i'的影響範圍不完全包含在j的影響範圍內，此時i的右側影響範圍大於等於[j-f[j]/2,i']，即i f[i]/ 2>=i'-j f[j]/2

由於對稱性，可得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 = &#39;#&#39;+&#39;#&#39;.join(self.string)+&#39;#&#39;        #字符串处理，用特殊字符隔离字符串，方便处理偶数子串 
    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耗時則為更短。

相關推薦：

python實作判斷一個字串是否是合法IP位址

Python針對給定字串求解所有子序列是否為回文序列的方法

以上是python最長回文串演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！