Knuth-Morris-Pratt-Suchalgorithmus: Implementierung in C Knuth-Morris-Pratt-Suchalgorithmus: Implementierung in C

Knuth-Morris-Pratt-Suchalgorithmus: Implementierung in C

2 months
0 Views
Want to watch this again later?
Sign in to add this video to a playlist. Login
0 0
Category:
Description:
Versuchsweise Implementierung des Knuth-Morris-Pratt-Suchalgorithmus in der Programmiersprache C, teils mit Erläuterung der theoretischen Grundlage. Siehe https://de.wikipedia.org/wiki/Knuth-Morris-Pratt-Algorithmus und https://www.geek-mom.de/2010/09/09/der-knuth-morris-pratt-algorithmus-leicht-erklart/.

Der Quelltext ist unter https://skreutzer.de/allerlei/knuth_morris_pratt.tar.gz zu finden.

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.