Explique le principe de fonctionnement de l'algorithme de recherche de sous-chaînes de Knuth-Morris-Pratt.

L’algorithme de Knuth-Morris-Pratt (KMP) est conçu pour rechercher une sous-chaîne dans une chaîne en temps linéaire, en évitant les comparaisons répétées de caractères.

L’idée principale est de calculer préalablement pour la sous-chaîne un tableau de fonctions de préfixe (ou « tableau π »), qui indique combien de caractères correspondent au début de la sous-chaîne lors d’une comparaison infructueuse. Cela permet, en cas de non-correspondance, de ne pas revenir au début de la chaîne d’origine, mais de décaler la sous-chaîne d’un nombre optimal de positions.

Exemple:

• Texte : "ABABDABACDABABCABAB"
• Recherche de la sous-chaîne : "ABABCABAB"

L’algorithme construit d’abord la fonction de préfixe pour la sous-chaîne, puis parcourt le texte en comparant les caractères. En cas de non-correspondance, il utilise la fonction de préfixe pour déterminer à partir de quel caractère de la sous-chaîne continuer la comparaison, sans repartir du début.

Cela garantit une complexité de O(n + m), où n est la longueur du texte, m la longueur de la sous-chaîne, ce qui est plus efficace que la recherche naïve.