Heim  >  Artikel  >  Backend-Entwicklung  >  elegante Python

elegante Python

黄舟
黄舟Original
2016-12-21 17:27:091513Durchsuche

Werfen wir zunächst einen Blick auf die einfache Zuordnung von Zeichenfolgen

Man kann sich das so vorstellen, als würde man die Textzeichenfolge s fixieren und die Musterzeichenfolge p beginnend mit der äußersten linken Seite von s ausrichten. Wenn die ausgerichteten Teile genau gleich sind, wenn die Übereinstimmung erfolgreich ist, wird die gesamte Musterzeichenfolge p um 1 Position nach rechts verschoben und der Ausrichtungsteil wird weiterhin überprüft und so weiter >


#Naive match

def naive_match(s , p):
m = len(s); n = len(p)
für i im Bereich (m-n+1):#Start pointer i
if s[i:i+ N] == P: Return true
Return false

Über den KMP-Algorithmus, das Beste Die Rede ist von Ruan Yifengs & lt; String-Matching-Algorithmus & gt;, der plötzlich aufgeklärt wird. Tatsächlich wird die Musterzeichenfolge p vorverarbeitet, um eine teilweise übereinstimmende Tabelle mit Suffixen und Suffixen zu erhalten um zu berechnen, wie viele Bits nach rechts verschoben werden können. Das heißt, kmp = naives Matching + Verschieben mehrerer Bits.
Weitere Informationen finden Sie im Artikel von Ruan Yifeng, der hier nicht näher erläutert wird.
Die Python Die Code-Implementierung ist unten angegeben.




#KMP
def kmp_match(s, p):

m = len(s); n = len(p)

cur = 0#Start pointer cur
table = Partial_table(p)
while cur<=m-n:
für i in range(n) :
if s[i+cur]!=p[i]:
cur += max(i - table[i-1], 1)# Mit der partiellen Matching-Tabelle verschieben wir nicht nur ein Bit nach rechts, kann aber mehrere Bits gleichzeitig verschieben
break
sonst:
true zurückgeben
false zurückgeben

#Partial Matching Table
def partial_table(p):
'''partial_table("ABCDABD") -> [0, 0, 0, 0, 1, 2, 0]''
prefix = set()
postfix = set()
ret = [0]
für i in range(1,len(p)):
prefix.add(p[:i])
postfix = {p[j:i+1] für j in range(1,i+1)}
ret.append(len((prefix&postfix or {''}).pop()))
return ret

print naive_match(" BBC ABCDAB ABCDABCDABDE", "ABCDABD")
print partial_table("ABCDABD")
print kmp_match ("BBC ABCDAB ABCDABCDABDE", "ABCDABD")



Das Obige ist Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website (www.php.cn)!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn