Knuth-Morris-Pratt-Algorithmus

Letztmalig dran rumgefummelt: 27.10.26 12:59:54

	Der Knuth-Morris-Pratt-Algorithmus (kurz KMP-Algorithmus) ist ein effizienter String-Matching-Algorithmus, der in einem Text nach einem bestimmten Suchmuster (Pattern) sucht. Funktionsweise & Vorteil • Das Problem des naiven Ansatzes: Ein einfacher Suchalgorithmus vergleicht Buchstabe für Buchstabe. Gibt es einen Fehler, rückt er das Muster um eine Stelle nach rechts und fängt vorne an. Das ist langsam! • Die KMP-Lösung: Der KMP-Algorithmus springt im Text niemals zurück. Er liest den Text genau einmal von links nach rechts. • Die Präfix-Tabelle (Failure-Function / Next-Array): Vor der eigentlichen Suche analysiert der Algorithmus das Suchmuster selbst. Er berechnet eine Sprungtabelle (oft LPS – Longest Proper Prefix which is also Suffix genannt). Diese Tabelle speichert, wie viele Zeichen beim Auftreten eines Fehlers übersprungen werden können, weil sie bereits als übereinstimmend bekannt sind.
	1. Zum Verfahren 2. ??? 3. ??? 4. Programmierung 5. Verwandte Themen
	Probleme & Problemlösungsverfahren   Logo des Knuth-Morris-Pratt-Algorithmus Download im CorelDraw-11-Format begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Basiswissen der Informatik Informatik-Profi-Wissen

1. Zum Verfahren

Der Knuth-Morris-Pratt-Algorithmus baut auf dem Naiven Suchalgorithmus auf. Wesentlicher Unterschied ist, dass das Vergleichsfenster nicht immer um nur eine Position weitergerückt wird, sondern eventuell um mehr als eine Position. Dazu muss zu Anfang die Suchmaske auf Zeichenfolgen analysiert werden, die ein möglichst langes Präfix des Musters selbst sind. Es wird vom Algorithmus dann eine Tabelle erstellt, die zu jedem Präfix der Länge j die Länge des echten Randes des Präfixes enthält, also die maximale Anzahl von Zeichen innerhalb des Präfixes des Suchmusters, die gleichzeitig Suffix und Präfix desselben sind. Es ist definiert, dass außerdem die Länge des echten Randes für ein Präfix der Länge null gleich −1 ist. Dies wird später im Algorithmus beim Suchen hilfreich sein.

Pseudocode bei VIRTUAL-LABS                   Pseudocode mit den entscheidenden Funktionen

2. ???

	D.
	UNICODE bei Wikipaedia

3. ???

4. Programmierung

	C-Programm bei Koding 4 Fun                 C-Programm mit den entscheidenden Funktionen

5. Verwandte Themen

das 8-Damen-Problem das Cliquenproblem das Dominoproblem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Wortproblem das Hamiltonproblem das K-Farben-Problem das Flaggenproblem das Halteproblem das Königsberger Brückenproblem das Philosophenproblem das Teilsummensummenproblem das Post'sche Korrespondenz-Problem das Rucksackprolem (Knapsackproblem) das Rundreiseproblem - aber: beachte die Mächtigkeit! das Springerproblem die Türme von Hanoi - mit hoher Anzahl von Scheiben wird das Problem praktisch nicht lösbar - 64 ist bereits enorm hoch das Knotenüberdeckungsproblem The Busy Beaver-Problem das Spannbaumproblem der Maze-Running-Algorithmus das Schachspiel Greedy Algorithm das Maximalflussproblem das Syntheseproblem   das k-Next-Neighbor-Problem   Schwarmintelligenz ... fehlererkennende Algorithmen -  ISBN-Nummer das Binärbaumproblem geometrischen Probleme Dijkstra-Algorithmus Fermat'sches Problem FERMAT's letzter Satz   ZIP-Algorithmus   Bresenham-Algorithmus   der Huffman-Code LZW-Kompression   Quadratsummen-Problem   die glücklichen & traurigen Zahlen   Smarandache-Wellin-Zahlen der austarierte Baum   Trunkierbare Primzahlen   FERMAT'scher Großer Satz   Eulerkreis   Lauflängen-Codierung   Zeichenkettenabgleich

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost am 27. Oktober 2026 um 11.39 Uhr