Pythons längster Palindrom-String-Algorithmus

Dieser Artikel stellt hauptsächlich die Praxis des längsten Palindrom-String-Algorithmus im Detail vor. Er hat einen gewissen Referenzwert.

Gegebenenfalls ist eine Zeichenfolge erforderlich. Finden Sie die längste Teilzeichenfolge in dieser Zeichenfolge entspricht der Palindrom-Eigenschaft. Das sogenannte Palindrom bezieht sich auf Zeichenfolgen wie „aba“, „ababa“, „abba“. Natürlich erfüllen auch ein einzelnes Zeichen und zwei benachbarte identische Zeichen die Palindrom-Eigenschaft.

Wenn man dieses Problem sieht, fällt einem natürlich als erstes die Brute-Force-Aufzählung ein, indem man die Startpunkte aller Strings in einem String auflistet, einen nach dem anderen die Teilstrings bestimmt, die das Palindrom erfüllen, die Länge aufzeichnet und Aktualisieren Sie die längste Länge. Offensichtlich ist die zeitliche Komplexität dieses Algorithmus sehr hoch und kann im schlimmsten Fall O(N*N) erreichen. Daher wird hier eine optimierte Lösung vorgeschlagen, indem die Mitte der Zeichenfolgen-Teilzeichenfolgen anstelle des Startpunkts aufgezählt und gleichzeitig auf beide Seiten verteilt wird. Die palindromische Natur der Teilzeichenfolgen wird weiterhin einzeln beurteilt. Dieser Optimierungsalgorithmus ist im schlimmsten Fall (also einer Zeichenfolge mit nur einem Zeichen) viel effizienter als der vorherige Algorithmus.

Aus dem obigen Optimierungsplan wissen wir, dass die Aufzählung des Zentrums effizienter ist als die Aufzählung der Punkte, aber dies ist nicht der optimale Algorithmus. Da der Algorithmus zum Aufzählen des Zentrums die Zeichen auf beiden Seiten des Zentrums gleichzeitig beeinflusst, können wir das Palindrom der Teilzeichenfolge beurteilen, indem wir die Zeichen links von der Mitte als Zentrum aufzählen und das Palindrom der Teilzeichenfolge beurteilen Zählt die Zeichen rechts von der Mitte als Mittelpunkt auf, dies ist der Manager-Algorithmus.

Die Idee des Manacher-Algorithmus ist sehr clever. Zuerst wird angenommen, dass i das Aufzählungszentrum ist, dann ist j (j

1 über j Der Einflussbereich des Zeichens i' ist vollständig im Einflussbereich von j enthalten, dann ist der Einflussbereich von i aufgrund des Palindroms größer oder gleich dem Einflussbereich von i', d. h. f[i] >=f[i']

2. Der Einflussbereich des Zeichens i', der symmetrisch zu j ist, ist zu diesem Zeitpunkt nicht vollständig im Einflussbereich von j enthalten Seite von i ist größer oder gleich [j-f[j]/2,i'], d. h. i +f[i]/2>=i'-j+f[j]/2

Aufgrund der Symmetrie können wir i+i" = 2*j erhalten. Daher ist im ersten Fall f[ i]>=f[2*j-i]; im zweiten Fall ist f[i]>= f[j]+2*j-2*i.

Zusammenfassend ergibt sich: f[i]>=min(f[2*j-i],f[j ]+2*j-2*i). immer noch hinter j+f[j]/2, was bedeutet, dass i nicht von den vorherigen Zeichen beeinflusst wird und nur nacheinander auf beide Seiten erweitert werden kann

Dieser Algorithmus muss die Zeichenfolge nur einmal durchlaufen. und die Anzahl der Erweiterungen ist begrenzt, sodass die Zeitkomplexität O(N) erreichen kann. Um die Effizienz des Algorithmus zu testen, stellt das Pthon3-Programm weiterhin den ursprünglichen Brute-Force-Aufzählungsalgorithmus bereit eine Referenz für den schlechtesten Algorithmus:

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

durch das obige Das Programm verwendet als Beispiel einen reinen 'a'-String mit einer Länge von 1000 . Nach dem Test:

Violent-Aufzählung: 49,719844s

Center-Aufzählung: 0,334019s

Manacher: 0,008000s

Das ist zu sehen Wenn die Länge 1000 beträgt, ist der Zeitaufwand einer gewaltsamen Aufzählung bereits unerträglich, und im Vergleich dazu ist die Effizienz der zentralen Aufzählung bereits eine deutliche Verbesserung, der optimale Manager benötigt weniger Zeit

Verwandte Empfehlungen:

Python-Implementierung, um festzustellen, ob eine Zeichenfolge eine zulässige IP-Adresse ist

Python-Methode, um herauszufinden, ob alle Teilsequenzen Palindromsequenzen für eine bestimmte Zeichenfolge sind

Das obige ist der detaillierte Inhalt vonPythons längster Palindrom-String-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!