algorithme de Knuth-Morris-Pratt

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 par Knuth et (en), et dans un autre contexte, par (en), et publié conjointement en 1977. Indépendamment Matiyasevich avait déjà obtenu dès 1969 un algorithme similaire, codé par une machine de Turing à deux dimensions, en étudiant un problème de reconnaissance d'occurrence de chaîne.