Algorithmes de recherche de sous-chaîne

Algorithme de recherche de sous-chaîne

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

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.

Rabin-Karp

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

Knuth-Morris-Pratt

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

Boyer-Moore

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

Aho-Corasick

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

Liens externes

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Algorithme de recherche de sous-cha%C3%AEne ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithmes de recherche de sous-chaîne de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Algorithme De Recherche De Sous-chaîne — 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… …   Wikipédia en Français

  • Algorithme de recherche de sous-chaine — Algorithme de recherche de sous chaîne 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… …   Wikipédia en Français

  • Algorithme de recherche de sous-chaîne — 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… …   Wikipédia en Français

  • Algorithme de recherche de chaîne de caractères de Boyer-Moore — Algorithme de Boyer Moore L algorithme de Boyer Moore est un algorithme de recherche de sous chaîne particulièrement efficace. Il a été développé par Bob Boyer et J. Strother Moore en 1977. Sommaire 1 Présentation 2 Fonctionnement de l algorithme …   Wikipédia en Français

  • Algorithme de recherche de sous-chaîne de Boyer-Moore — Algorithme de Boyer Moore L algorithme de Boyer Moore est un algorithme de recherche de sous chaîne particulièrement efficace. Il a été développé par Bob Boyer et J. Strother Moore en 1977. Sommaire 1 Présentation 2 Fonctionnement de l algorithme …   Wikipédia en Français

  • Algorithmes de recherche — Algorithme de recherche Pour les articles homonymes, voir recherche (homonymie). En informatique, un algorithme de recherche est un type d algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne en résultat un… …   Wikipédia en Français

  • Algorithme De Recherche — Pour les articles homonymes, voir recherche (homonymie). En informatique, un algorithme de recherche est un type d algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne en résultat un ensemble de solutions… …   Wikipédia en Français

  • Algorithme de recherche — Pour les articles homonymes, voir recherche (homonymie). En informatique, un algorithme de recherche est un type d algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne en résultat un ensemble de solutions… …   Wikipédia en Français

  • Chaine De Caractères — Chaîne de caractères En informatique, une chaîne de caractères est une suite ordonnée de caractères. La chaîne de caractères est un type de donnée dans de nombreux langages informatiques. En anglais, on emploie le terme (en) string. Sommaire 1… …   Wikipédia en Français

  • Chaine de caracteres — Chaîne de caractères En informatique, une chaîne de caractères est une suite ordonnée de caractères. La chaîne de caractères est un type de donnée dans de nombreux langages informatiques. En anglais, on emploie le terme (en) string. Sommaire 1… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”