Wann ist es gut, den KMP-Algorithmus zu verwenden?

Question

Ich verstehe, dass KMP-Algorithmus hängt von der Helfer-Array, dass es Präfixe, die Suffixe ähnlich sind. Es wird nicht effizient, wenn die obige Bedingung nicht erfüllt ist, da im Helper-Array alle Nullen enthält. Wäre die Laufzeit O (m + n)? Wenn ich richtig bin, was ist ein besser Teilstring-Algorithmus in diesem Fall?

Answer 1

Um zu verstehen, wann KMP ein guter Algorithmus ist, ist es oft hilfreich, die Frage "Was ist die Alternative?" Zu stellen.

KMP hat den Vorteil, dass es im ungünstigsten Fall effizient ist. Die Vorlaufzeit ist immer O (n) und die Suchzeit ist immer O (m). Es gibt keine Worst-Case-Inputs, keine Wahrscheinlichkeit, Pech zu haben, etc. In Fällen, in denen Sie sehr lange Strings (large n) innerhalb wirklich großer Strings (large m) suchen, kann dies im Vergleich zu anderen Algorithmen sehr wünschenswert sein der naive (der in schlechten Fällen Zeit braucht Θ (Mn)), Rabin-Karp (pathologische Eingaben können Zeit brauchen Θ (Mn)), oder Boyer-Moore (Worst-Case kann Θ (Mn) sein). Sie haben recht, dass KMP nicht unbedingt notwendig ist, wenn es nicht viele überlappende Teile der Saite gibt, aber die Tatsache, dass Sie sich nie darum kümmern müssen, ob es einen schlechten Fall gibt, ist definitiv eine gute Sache!

KMP hat auch die nette Eigenschaft, dass die Verarbeitung ein einziges Mal durchgeführt werden kann. Wenn Sie wissen, dass Sie nach dem gleichen Teilstring viele Male suchen werden, können Sie die O (n) Preprocessing-Arbeit einmal durchführen und dann die Möglichkeit haben, in einer beliebig langen Länge zu suchen (m).