Eine kurze Ausarbeitung zum Knuth-Morris-Pratt Algorithmus von 1977. In dieser Seminararbeit wird die anschaulichere, weniger theoretische Herangehensweise von Morris erläutert. Dazu wird im ersten Schritt der naive Suchalgorithmus vorgestellt und darauf aufbauend werden dann die Verbesserungen durch den KMP-Algorithmus nachvollzogen.
Für verschiedene Anwendungen ergibt sich die Aufgabenstellung, in einem Text ein bestimmtes Suchmuster (engl. Pattern) zu finden. Dabei kann der Text sehr groß sein. Deshalb ist es wichtig, dass der verwendete Algorithmus effizient ist und auch für große Datensätze eine kurze Laufzeit aufweist. Der Knuth-Morris-Pratt Algorithmus ist ein Ansatz, diese Aufgabe zu erfüllen.
Inhalt
1. Einleitung
2. Grundlagen/Begrifflichkeiten
3. Naiver Suchalgorithmus
3.1. Definition
3.2. Stringmatching am Beispiel
3.3. Laufzeitanalyse
3.3.1. Worst case
3.3.2. Best case
3.3.3. Average case
4. KMP-Algorithmus
4.1. Grundidee
4.2. Präfix-Suffix Array
4.3. Stringmatching am Beispiel
4.4. Laufzeitanalyse
5. Laufzeitvergleich
6. Anwendung
7. Zusammenfassung
8. Literaturverzeichnis
9. Tabellenverzeichnis
10. Quellcodeverzeichnis
11. Abbildungsverzeichnis
12. Anhang
- Quote paper
- Johannes Dieker (Author), 2019, Der Knuth-Morris-Pratt Algorithmus von 1977, Munich, GRIN Verlag, https://www.hausarbeiten.de/document/1185621