Algorithmus:
Der Knuth-Morris-Pratt-Algorithmus vergleicht wie im primitiven Ansatz den Text mit dem Muster,
versucht aber bei einem Mismatch möglichst weit im Text weiterzuspringen.
Hierfür wird eine Tabelle erstellt, indem das Muster mit sich selbst verglichen wird.
Komplexität:
Die amortisierte Analyse liefert 
.