4
Damit der Boyer-Moore-Algorithmus im schlechtesten Fall linear ist, muss die Berechnung der Mismatch-Tabelle O (m) sein. Eine naive Implementierung würde jedoch alle Suffixe O (m) und alle Positionen durchlaufen, in denen das Suffix hingehen und auf Gleichheit prüfen könnte ... was 0 ist (m)!Berechnung der zweiten Tabelle (mis-match) im String-Suchalgorithmus nach Boyer-Moore
Unten ist die naive Implementierung von table building algorithm. Diese Frage wird also: Wie kann ich die Laufzeit dieses Algorithmus zu O (m) verbessern?
def find(s, sub, no):
n = len(s)
m = len(sub)
for i in range(n, 0, -1):
if s[max(i-m, 0): i] == sub[max(0, m-i):] and \
(i-m < 1 or s[i-m-1] != no):
return n-i
return n
def table(s):
m = len(s)
b = [0]*m
for i in range(m):
b[i] = find(s, s[m-i:], s[m-i-1])
return b
print(table('anpanman'))
Um den Geist in Ruhe zu versetzen, ist dies keine Hausaufgabe. Ich werde Revisionen hinzufügen, wenn jemand Ideen für Verbesserungen veröffentlicht.
Für eine Sache, verwenden Sie Xrange (n, 0, -1) und Xrange (M) anstelle von Bereich() ... es spart ein wenig Speicher –
Eigentlich ist der obige Code Python 3. Siehe http://docs.python.org/dev/py3k/library/functions.html?highlight=range#range –
Wie wäre es mit der Implementierung von LiteratePrograms? Es scheint, als ob es weniger Vorverarbeitung, aber ich bin kein Boyer-Moore-Experte. http://en.literateprograms.org/Boyer-Moore_string_search_algorithm_(Python) – hao