Algorithme de recherche de sous-chaîne

vignette|Illustration de la recherche de la sous-chaîne "long des" dans la première strophe du poème Chanson d'automne de Paul Verlaine. En algorithmique du texte, un algorithme de recherche de sous-chaîne est un type d'algorithme de recherche qui a pour objectif de trouver une chaîne de caractères dans un texte. Le problème de recherche d'une sous-chaîne intervient dans beaucoup d'applications. Par exemple, dans un logiciel de traitement de texte, ou dans un navigateur internet, l'utilisateur peut rechercher une chaîne de caractères dans un document, ou une page Internet, en vue de remplacer un mot par un autre (par exemple, remplacer toues les occurrences du mot "rêve" par le mot "songe"). La plupart des langages de programmation proposent des fonctions pour effectuer une telle recherche ; par exemple en Python, on écrit chaine in texte pour tester si la chaîne apparaît dans le texte. Par extension, on peut considérer aussi le problème de trouver toutes les occurrences d'un mot, ou alors de compter le nombre d'occurrences d'une chaîne dans un texte. L'algorithme naïf consiste consiste à faire glisser le motif le long du texte. A début, le motif se trouve aligné avec le début du texte. Par exemple si l'on cherche la chaîne longs des dans le texte les sanglots longs des violons de l'automne blessent mon cœur d'une langueur monotone on considère l'alignement suivant : les sanglots longs des violons de l'automne blessent mon cœur d'une langueur monotone. longs des On compare caractère après caractère le motif et le texte. Le première caractère est l. Mais le deuxième caractère est différent. On fait alors glisser le motif d'une case vers la droite. les sanglots longs des violons de l'automne blessent mon cœur d'une langueur monotone. longs des On compare caractère après caractère le motif et le texte à partir du second caractères. Le caractère e et l sont différents. On continue donc à glisser le motif. les sanglots longs des violons de l'automne blessent mon cœur d'une langueur monotone.