Looking for algorithm Keywords? Try Ask4Keywords

algorithmKnuth Morris Pratt (KMP) Algorithmus


Einführung

Der KMP ist ein Musterabgleichungsalgorithmus, der nach Vorkommen eines "Wortes" W innerhalb einer Haupt- "Textzeichenfolge" S sucht, indem er die Beobachtung verwendet, dass, wenn eine Nichtübereinstimmung auftritt, wir über ausreichende Informationen verfügen, um zu bestimmen, wo die nächste Übereinstimmung beginnen könnte Nutzen Sie diese Informationen, um zu vermeiden, dass die Zeichen, von denen wir wissen, dass sie auf jeden Fall übereinstimmen, übereinstimmen. Die Komplexität der Suche nach einem Muster reduziert sich auf 0 (n) .

Knuth Morris Pratt (KMP) Algorithmus Verwandte Beispiele