Algoritmo di Knuth-Morris-Pratt
Da Wikipedia, l'enciclopedia encyclopedia
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 Pratt, e indipendentemente da J. H. Morris nel 1975.