Python implementiert die Suche nach der längsten sich nicht wiederholenden Teilzeichenfolge für eine bestimmte Zeichenfolge

In diesem Artikel wird hauptsächlich Pythons Methode zum Finden des längsten sich nicht wiederholenden Teilstrings für einen bestimmten String vorgestellt, einschließlich Pythons Durchlauf-, Sortier-, Berechnungs- und anderen verwandten Operationsfähigkeiten für Strings. Freunde in Not können sich darauf beziehen.

Das Beispiel in diesem Artikel beschreibt die Methode zum Finden des längsten sich nicht wiederholenden Teilstrings für einen bestimmten String in Python. Geben Sie es wie folgt als Referenz an alle weiter:

Frage:

Suchen Sie bei einer gegebenen Zeichenfolge die längste sich wiederholende Teilsequenz darin, wenn Besteht die Zeichenfolge aus einem einzelnen Zeichen, z. B. „aaaaaaaaaaaaa“, dann ist die Ausgabe, die die Anforderungen erfüllt, eine

Idee:

Die Idee hier ist: Die beiden fallen mir ein

(1) Durchlaufen Sie die Zeichenfolge von Anfang an, setzen Sie das Flag-Bit und stellen Sie fest, dass es mit dem vorherigen Flag-Bit übereinstimmt Gehen Sie zurück, gehen Sie zurück und prüfen Sie, ob die Teilzeichenfolge mit der vorherigen Zeichenfolge oder der Teilzeichenfolge der vorherigen Zeichenfolge identisch ist. Wenn sie identisch ist, wird die Teilzeichenfolge aufgezeichnet und die Anzahl um 1 erhöht, bis die Verarbeitung abgeschlossen ist abgeschlossen

(2) Verwenden Sie den Schiebefenster-Slice-Mechanismus, um alle Slices zu generieren. Als Nächstes verwenden Statistiken und Verarbeitung hauptsächlich die Funktion der doppelten Sortierung.

Dieser Artikel verwendet die zweite Methode. Das Folgende ist die spezifische Umsetzung:

#!usr/bin/env python
#encoding:utf-8
'''''
__Author__:沂水寒城
功能：给定一个字符串，寻找最长重复子串
'''
from collections import Counter
def slice_window(one_str,w=1):
  '''''
  滑窗函数
  '''
  res_list=[]
  for i in range(0,len(one_str)-w+1):
    res_list.append(one_str[i:i+w])
  return res_list
def main_func(one_str):
  '''''
  主函数
  '''
  all_sub=[]
  for i in range(1,len(one_str)):
    all_sub+=slice_window(one_str,i)
  res_dict={}
  #print Counter(all_sub)
  threshold=Counter(all_sub).most_common(1)[0][1]
  slice_w=Counter(all_sub).most_common(1)[0][0]
  for one in all_sub:
    if one in res_dict:
      res_dict[one]+=1
    else:
      res_dict[one]=1
  sorted_list=sorted(res_dict.items(), key=lambda e:e[1], reverse=True)
  tmp_list=[one for one in sorted_list if one[1]>=threshold]
  tmp_list.sort(lambda x,y:cmp(len(x[0]),len(y[0])),reverse=True)
  #print tmp_list
  print tmp_list[0][0]
if __name__ == '__main__':
  print "脚本之家测试结果："
  one_str='abcabcd'
  two_str='abcabcabd'
  three_str='bbbbbbb'
  main_func(one_str)
  main_func(two_str)
  main_func(three_str)

Die Ergebnisse sind wie folgt:

Verwandte Empfehlungen:

Python implementiert die Methode zur Ausgabe einer Zahl in umgekehrter Reihenfolge gemäß den angegebenen Anforderungen

Python implementiert die Methode der Eingabe mehrerer Zeilen in IDLE

Das obige ist der detaillierte Inhalt vonPython implementiert die Suche nach der längsten sich nicht wiederholenden Teilzeichenfolge für eine bestimmte Zeichenfolge. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!