algorithme de chaîne de palindrome le plus long de Python

Cet article présente principalement en détail la pratique de l'algorithme de chaîne palindrome la plus longue de Python. Il a une certaine valeur de référence. Les amis intéressés peuvent s'y référer

Étant donné une chaîne, les exigences Trouver la sous-chaîne la plus longue de cette chaîne. est conforme à la propriété palindrome. Le soi-disant palindrome fait référence à des chaînes telles que « aba », « ababa », « abba ». Bien entendu, un seul caractère et deux caractères identiques adjacents satisfont également à la propriété du palindrome.

En voyant ce problème, la première solution qui vient à l'esprit est naturellement l'énumération par force brute. En énumérant les points de départ de toutes les chaînes d'une chaîne, on détermine une par une les sous-chaînes qui satisfont au palindrome, on enregistre la longueur et mettre à jour la longueur la plus longue. Évidemment, la complexité temporelle de cet algorithme est très élevée, et peut atteindre O(N*N) dans le pire des cas. Par conséquent, une solution optimisée est proposée ici. En énumérant le centre des sous-chaînes de chaînes au lieu du point de départ, en s'étendant des deux côtés en même temps, la nature palindromique des sous-chaînes est toujours jugée une par une. Cet algorithme d'optimisation est bien plus efficace que l'algorithme précédent dans le pire des cas (c'est-à-dire une chaîne avec un seul caractère).

D'après le plan d'optimisation ci-dessus, nous savons qu'énumérer le centre est plus efficace que d'énumérer le point, mais ce n'est pas l'algorithme optimal. Puisque l'algorithme d'énumération du centre affecte les caractères des deux côtés du centre en même temps, nous pouvons juger du palindrome de la sous-chaîne en énumérant les caractères à gauche du centre comme centre et en jugeant le palindrome de la sous-chaîne qui énumère les caractères à droite du centre comme center , c'est l'algorithme du gestionnaire.

L'idée de l'algorithme manacher est très intelligente. Premièrement, il traverse la chaîne. Supposons que i soit le centre d'énumération, puis j (j

1 i est symétrique. à propos de j La plage d'influence du caractère i' est complètement incluse dans la plage d'influence de j, alors en raison du palindrome, la plage d'influence de i est supérieure ou égale à la plage d'influence de i', c'est-à-dire f[i] >=f[i']

2. La plage d'influence du caractère i' qui est symétrique par rapport à j n'est pas complètement incluse dans la plage d'influence de j À l'heure actuelle, la plage d'influence de la droite. le côté de i est supérieur ou égal à [j-f[j]/2,i'], c'est-à-dire i +f[i]/2>=i'-j+f[j]/2

En raison de la symétrie, nous pouvons obtenir i+i" = 2*j. Par conséquent, dans le premier cas, f[ i]>=f[2*j-i] ; dans le second cas, f[i]>= f[j]+2*j-2*i

En résumé, 1,2. On peut obtenir que f[i]>=min(f[2*j-i],f[j. ]+2*j-2*i). Puisqu'il y a des caractères non traversés sur le côté droit de i, sur cette base, continuez vers les deux côtés jusqu'à ce que la sous-chaîne palindrome la plus longue soit trouvée

Si i est. toujours derrière j+f[j]/2, cela signifie que i n'est pas affecté par les caractères précédents et ne peut être étendu des deux côtés qu'un par un

Cet algorithme n'a besoin de parcourir la chaîne qu'une seule fois, et le nombre d'expansions est limité, donc la complexité temporelle peut atteindre O(N).

Ce qui suit est le programme Pthon3, afin de tester l'efficacité de l'algorithme, fournit toujours l'algorithme d'énumération par force brute d'origine. une référence pour le pire algorithme :

#求最长回文串类 
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            #去除特殊字符

Grâce au programme ci-dessus, en utilisant une chaîne 'a' pure d'une longueur de 1000 comme exemple, testé :

Dénombrement violent : 49,719844s

Dénombrement centre : 0,334019s

manacher : 0,008000s

On voit que lorsque la longueur est de 1000, le temps d'un dénombrement violent est insupportable, et en comparaison, l'efficacité du dénombrement central est Il y a eu une amélioration significative et le gestionnaire optimal prend moins de temps

Recommandations associées :

Implémentation Python pour déterminer si une chaîne est une adresse IP légale

Méthode Python pour savoir si toutes les sous-séquences sont des séquences palindromes pour une chaîne donnée

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!