Algorithme de recherche de sous-chaîne
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
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.
Sommaire |
[modifier] Algorithme naïf
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.
[modifier] Rabin-Karp
Article détaillé - Algorithme de Rabin-Karp.
[modifier] Knuth-Morris-Pratt
Article détaillé - Algorithme de Knuth-Morris-Pratt.
[modifier] Boyer-Moore
Article détaillé - Algorithme de Boyer-Moore.
[modifier] Lien externe
- (en) Algorithme de recherche de chaine
- (en) StringSearch – high-performance pattern matching algorithms in Java – implémentations des algorithmes BNDM, Boyer-Moore-Horspool, Boyer-Moore-Horspool-Raita et Shift-Or en Java
