« Algorithme d'Aho-Corasick » : différence entre les versions

De manière informelle, l'algorithme génère un arbre avec des liens entre les nœuds. Chaque nœud représentant une chaîne (par exemple <code>abc</code>) a un lien vers le nœud qui correspond au plus long suffixe disponible (dans le cas d'<code>abc</code>, il s'agit de <code>bc</code> s'il existe, autrement <code>c</code> ou encore la racine). De plus l'arbre maintient des liens entre un nœud donné et le nœud représentant le suffixe le plus long qui apparaît dans le dictionnaire. Les correspondances peuvent ainsi être énumérées en parcourant la liste chaînée. L'algorithme utilise ensuite l'arbre pendant l'exécution, se déplaçant progressivement dans le texte en entrée et en conservant la correspondance la plus longue. L'utilisation de l'arbre garantit une complexité linéaire. Pour chaque nœud présent dans le dictionnaire et tout lien dans la liste chaînée des suffixes du dictionnaire, une sortie est générée.

 

 

== Applications et historique ==