Algorithme de Knuth-Morris-Pratt

Carte Commune · n° 242120

En informatique, 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. Il permet de trouver les occurrences d'une chaîne P (ou aussi appelé motif) dans un texte T avec une complexité linéaire O(|P|+|T|) dans le pire cas, où |P| et |T| sont respectivement les longueurs (nombres de caractères) de la chaîne P et du texte T et O() est une notation asymptotique de Landau. De plus la constante dans le O() ne dépend pas de la taille de l'alphabet. 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. Plus précisément, la complexité du prétraitement est en O(|P|), et la recherche proprement dite est en O(|T|). L'algorithme a été conçu en 1970 par Knuth et Pratt...

Lire sur Wikipédia · Image Fschwarzentruber, CC BY-SA 4.0