Algoritmo di Knuth-Morris-Pratt

L'algoritmo di Knuth-Morris-Pratt (spesso abbreviato come algoritmo KMP) è un algoritmo di pattern matching su stringhe, che permette di trovare le occorrenze di una stringa (pattern) in un testo . La sua peculiarità risiede nel pretrattamento della stringa da cercare, la quale contiene l'indicazione sufficiente a determinare la posizione da cui continuare la ricerca in caso di non-corrispondenza. Questo permette all'algoritmo di non riesaminare i caratteri che erano stati precedentemente verificati, e dunque di limitare il numero di confronti necessari. L'algoritmo è stato inventato da Knuth e , e indipendentemente da nel 1975.