Knuth-Morris-Pratt-Suchalgorithmus: Implementierung in C
Versuchsweise Implementierung des Knuth-Morris-Pratt-Suchalgorithmus in der Programmiersprache C, teils mit Erläuterung der theoretischen Grundlage. Siehe http://de.wikipedia.org/wiki/Knuth-Morris-Pratt-Algorithmus und http://www.geek-mom.de/2010/09/09/der-knuth-morris-pratt-algorithmus-leicht-erklart/.
Der Quelltext ist unter http://www.skreutzer.de/allerlei/knuth_morris_pratt.tar.gz zu finden.
Nun, an einigen Stellen könnte man noch etwas verbessern - wahrscheinlich kann die Bedingung in der for-Suchschleife einfacher formuliert werden. Das Beispiel mit „aba“ gegen „ababa“ sollte eher lauten „ababa“ gegen „abababa“, um den Effekt besser zu verdeutlichen. Dort habe ich mich auch in den Positionen verzählt und die Aussage, dass man das „ab“ zu Beginn beim erfolgreichen Finden des Suchbegriffs überspringen könne, ist in diesem Beispiel nicht korrekt, denn das „b“ war nicht Teil des Präfixes.
Der Quelltext ist unter http://www.skreutzer.de/allerlei/knuth_morris_pratt.tar.gz zu finden.
Nun, an einigen Stellen könnte man noch etwas verbessern - wahrscheinlich kann die Bedingung in der for-Suchschleife einfacher formuliert werden. Das Beispiel mit „aba“ gegen „ababa“ sollte eher lauten „ababa“ gegen „abababa“, um den Effekt besser zu verdeutlichen. Dort habe ich mich auch in den Positionen verzählt und die Aussage, dass man das „ab“ zu Beginn beim erfolgreichen Finden des Suchbegriffs überspringen könne, ist in diesem Beispiel nicht korrekt, denn das „b“ war nicht Teil des Präfixes.
Category:
More From: skreutzer
Related Videos
2 ratings
24 views
Want to add this video to your favorites?
Sign in to VidLii now!
Sign in to VidLii now!
Want to add this video to your playlists?
Sign in to VidLii now!
Sign in to VidLii now!
Want to flag this video?
Sign in to VidLii now!
Sign in to VidLii now!
Video Responses (0)
Sign in to make a video response
Text Comments (0)
Sign in to post a comment
Date: |
Views: 24 | Ratings: 2 |
Time: | Comments: 0 | Favorites: 0 |