Zitat von
stoxx:
Ein Bayer Moore Algorithmus hat ja immer noch die Laufzeit O(m/n).
Also erstens heißt das Boyer-Moore, und zweitens hat das Ding im Mittel ne Laufzeit von O(log(n)/n * m) (log zur Basis der Alphabetgröße, aber das ist ja egal). Im Worst-Case ist die Laufzeit O(m*n) bzw. O(m), je nachdem welche Boyer-Moore-Variante man nun genau nimmt (Wikipedia nicht fragen, da steht teilweise Stuss.) O(1), wenn m=n ist, ist auch Quatsch - wenn das Muster gleich dem Text ist, muss man das ja überprüfen, man hat also m Schritte im Worst-Case, einen im Best-Case, also O(m) im Mittel.
Ich habe nicht den ganzen Thread gelesen, aber der Algorithmus ganz oben sieht sehr nach Quicksearch (von Sunday) aus, eine Variante von Boyer-Moore-Horspool. Diese beiden Algorithmen sind in vielen Anwendungsgebieten die schnellsten bekannten Algorithmen (ja, schneller als der Standard-Boyer-Moore!). Zumindest für den Fall, dass man den zu durchsuchenden Text nicht aufbereitet, sondern nur das Suchmuster, aber das ist ja ne ganz andere Herangehensweise.
Für kleine Alphabete (z.B. für eine Suche in DNS-Sequenzen) eignen sich dann allerdings andere Algorithmen besser. Da wären die Faktor-basierten Algorithmen (die auch mit Suffix-Trees arbeiten) besser, oder die sogenannten Faktor-Orakel, die so um 2001 das "erfunden" wurden.
Ansonsten ist der Algorithmus im ersten Beitrag sehr zu empfehlen, und eine Optimierung halte ich im Gegnsatz zu meinem Vorredner für durchaus sinnvoll.
