Algorithme 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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme 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 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 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… …   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 — 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

  • 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 2.1 Pré traitement …   Wikipédia en Français

  • Algorithme De Knuth-Morris-Pratt — L algorithme de Knuth Morris Pratt (souvent abrégé par algorithme KMP) est un algorithme de recherche de sous chaîne, permettant de trouver les occurrences d une chaîne P dans un texte S. Sa particularité réside en un pré traitement de la chaîne …   Wikipédia en Français

  • Algorithme KMP — Algorithme de Knuth Morris Pratt L algorithme de Knuth Morris Pratt (souvent abrégé par algorithme KMP) est un algorithme de recherche de sous chaîne, permettant de trouver les occurrences d une chaîne P dans un texte S. Sa particularité réside… …   Wikipédia en Français

Share the article and excerpts

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