Diskussion:Knuth-Morris-Pratt-Algorithmus
Bitte hört auf an diesem Artikel rumzufingern wenn Ihr den Algo nicht *Verstanden* habt.
Zur vorigen Diskussion[Quelltext bearbeiten]
Ränder[Quelltext bearbeiten]
Den Begriff Rand extra einzuführen und nur einmal zu benutzen ist verwirrend. Außerdem wird nicht klar daß die Präfixe in der Präfix-Tabelle an der Stelle stehen an der sie im Muster nochmal aufgetreten sind.
Auch wäre im Beispiel 'a' an Position 0 ein Präfix (Rand der Länge 1), das aber von KMP nicht betrachtet wird. Deswegen ist die Erklärung mit Rändern auch sachlich falsch.
Daß bei der Präfix-Berechnung nicht bei der ersten Stelle des Musters begonnen werden kann sieht man auch wenn man sich klar macht daß per Definition jeder Anfang des Musters natürlich ein Präfix des Musters ist. Man ist ja gerade daran interessiert, wo doe Muster im Text *noch* auftreten, insbesondere also nicht am Anfang.
Von Daher kann man schon Sagen daß man die Ränder der Präfixe sucht. Allerdings müßte man dann sagen daß man sich für jedes Präfix die zweite Startposition seines Randes merkt.
Habe versucht, einiges klarzustellen, letzter Abschnitt: Evtl. vereinfachen, eigentlich ist die Tabelle so etwas unübersichtlich, die Erklärung scheint aber kongruent. --E01f (Diskussion) 16:36, 25. Jul. 2013 (CEST)
Laufzeit[Quelltext bearbeiten]
Wer den Artikel aufmerksam liest, findet an mehreren Stellen den Hinweis daß der Algo *alle* Treffer ausgibt. Insbesondere hören wir nicht beim ersten Treffer auf, und finden *auch überlappende* Treffer. Der Algo könne "viel früher" terminieren ist also Quatsch! => Theta statt Oh
Vergleich mit Boyer-Moore[Quelltext bearbeiten]
Der Satz zum Vergleich mit Boyer-Moore ist falsch! Die Worst-Case Laufzeit von BM beträgt nämlich nicht O(N*M), sondern nur O(N+M). Die Variante, auf die hier wahrscheinlich verwiesen wird, ist der Boyer-Moore-Horspool Algorithmus, der nur eine der beiden möglichen Verschiebungen benutzt und so Speicherplatz für Zeit tauscht. Der eigentliche Boyer-Moore Algorithmus braucht nur O(N+M), auch wenn der Beweis recht aufwändig ist. -- 87.123.40.120 15:43, 18. Apr. 2009 (CEST)