Algoritmos/Reconhecimento de padrões/Algoritmo Aho Corasick

Origem: Wikilivros, livros abertos por um mundo aberto.
< Algoritmos‎ | Reconhecimento de padrões
Saltar para a navegação Saltar para a pesquisa

Algoritmo de Aho-Corasick foi inventado por Alfred V. Aho e Margaret J. Corasick, em 1975. É um algoritmo de pesquisa de String que encontra elementos de um conjunto finito de padrões (o "dicionário") dentro de um texto de entrada. Encontra todos os padrões "em uma vez", assim do algoritmo é linear de acordo com o tamanho dos padrões mais o tamanho da String de busca. A implementação desse algoritmo é baseada em uma arvore Trie.

Exemplo:

Input: text = "ahishers"    
       arr[] = {"he", "she", "hers", "his"}

Output:
   A palavra his aparece na posição 1 a 3
   A palavra he aparece na posição 4 a 5
   A palavra she aparece na posição 3 a 5
   A palavra hers aparece na posição 4 a 7