Algorithme de Knuth-Morris-Pratt
De Wikipedia, l'encyclopédie encyclopedia
L'algorithme de Knuth-Morris-Pratt (ou d'une manière plus courte l'algorithme KMP) est un algorithme de recherche de sous-chaîne (de caractères), permettant de trouver les occurrences d'une chaîne dans un texte avec une complexité linéaire dans le pire cas. Sa particularité réside en un pré-traitement de la chaîne, qui fournit une information suffisante pour déterminer où continuer la recherche en cas de non-correspondance. Ainsi l'algorithme ne ré-examine pas les caractères qui ont été vus précédemment, et donc limite le nombre de comparaisons nécessaires.
L'algorithme a été conçu en 1970[1] par Knuth et Pratt (en), et dans un autre contexte, par Morris (en), et publié conjointement en 1977[2]. Indépendamment Matiyasevich[3],[4] avait déjà obtenu dès 1969 un algorithme similaire, codé par une machine de Turing à deux dimensions[pas clair], en étudiant un problème de reconnaissance d'occurrence de chaîne.