Führt der KMP (Knuth-Morris-Pratt) Algorithmus weniger Vergleiche durch als der vereinfachte Boyer-Moore Algorithmus?Führt der KMP-Algorithmus weniger Vergleiche durch als der vereinfachte Boyer-Moore-Algorithmus?
Der Boyers Moore-Algorithmus sollte in der Regel mit weniger Vergleiche durchführen von here
Es sollte einigermaßen klar sein, zu zitieren, wenn es normalerweise der Fall ist, dass ein bestimmter Brief tut überhaupt in der Suchzeichenfolge erscheinen, dann benötigt dieser Algorithmus nur ungefähr N/M Zeichenvergleiche (N = Länge (s1), M = Länge (s2)) - eine große Verbesserung gegenüber dem KMP-Algorithmus, der N noch benötigt. Wenn dies jedoch nicht der Fall ist kann wieder bis zu N + M Vergleiche benötigen (mit der Vollversion des Algorithmus). Glücklicherweise kommen wir bei vielen Anwendungen der N/M-Leistung nahe. Wenn der Suchstring sehr groß ist, dann ist es wahrscheinlich, dass ein bestimmtes Zeichen darin erscheint, aber wir erhalten immer noch eine gute Verbesserung im Vergleich zu den anderen Algorithmen (ca. N * 2/alphabet_größe, wenn Zeichen zufällig in einem String verteilt sind).
Ich habe einige Tests vor vielen Jahren gemacht. B-M gewann jedes Mal über KMP. – EJP