entwickeltes boyer-moore program läuft nich

[Gausi]

Bist du sicher, dass deine Implementierung von KMP den Text ganz durchsucht hat, und nicht (wie pos) beim ersten Treffer aufgehört hat? Bei meinen Tests ist KMP um den Faktor 2-3 schneller. Selbst eine einfache Implementierung des "naiven Verfahrens" ist schneller als pos.
KMP ist aber wirklich eher theoretisch interessant, weil das einer der ersten Stringsuche-Algorithmen ist, die eine linare Worst-Case Laufzeit haben. Gegen einen anständig programmierten Boyer-Moore-Horspool oder Sunday kann es nichts ausrichten - zumindest nicht dann, wenn die gesuchten Substrings eine gewisse Länge überschreiten (so 5-10 Zeichen vielleicht).

Pos ist natürlich dann schneller, wenn man in sehr kurzen Texten sucht - dann schlägt die Vorbereitungszeit für KMP durch. Aber ansonsten ist pos was die Performance angeht, ab Texten von 50kb deutlich allen anderen Verfahren unterlegen. Und wenn man in vielen kurzen Texten sucht (z.B. ne Stringlist zeilenweise durchsucht), kann man die Vorbereitung für kmp einmal machen und nur die Suchphase wiederholen.

Zwei Beispiele:

10mb DNS-Sequenz, 300 Zeichen langes Muster. pos: ca. 200ms, kmp: ca. 70ms, "akademischer Kramladen-Algorithmus": knapp 4ms. [edit: hier ist die Einheit natürlich ms, nicht µs]

10kb langer Text, 15 Zeichen langes Muster. pos: 70µs, kmp: 63µs, "anderer akademischer Kramladen-Algorithmus": knapp 7µs.