Algorithme de recherche de sous-chaîne

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un algorithme de recherche de sous-chaine est un type d'algorithme de recherche qui a pour objectif de trouver une chaîne de caractères à l'intérieur d'une autre. Un tel algorithme fournit la position du premier caractère de la sous-chaîne recherchée dans la chaîne fournie en entrée.

Algorithme naïf[modifier | modifier le code]

L'idée est de réaliser une comparaison caractère après caractère de la chaîne initiale et de la chaîne recherchée. On parcourt les caractères de la chaîne initiale tant qu'ils sont différents du premier caractère de la chaîne à trouver. Dès qu'on trouve un caractère identique, on parcourt les caractères suivants tant qu'ils correspondent. Si un caractère diffère alors qu'on n'a pas atteint la fin de la chaîne recherchée, alors on reprend la recherche du premier caractère identique, à partir du caractère suivant dans la chaîne initiale. Si tous les caractères correspondent, on retourne la position du premier caractère de la chaîne trouvée dans la chaîne initiale. Enfin, si aucune occurrence de la chaîne recherchée n'apparaît dans la chaîne initiale, l'algorithme se doit de le signaler, en retournant une valeur négative par exemple.

Rabin-Karp[modifier | modifier le code]

Article détaillé - Algorithme de Rabin-Karp.

Knuth-Morris-Pratt[modifier | modifier le code]

Article détaillé - Algorithme de Knuth-Morris-Pratt.

Boyer-Moore[modifier | modifier le code]

Article détaillé - Algorithme de Boyer-Moore.

Aho-Corasick[modifier | modifier le code]

Article détaillé - Algorithme d'Aho-Corasick.

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]