---
title: "Algoritmo Aho-Corasick em Rust"
url: "https://rustlang.com.br/algoritmos/aho-corasick/"
markdown_url: "https://rustlang.com.br/algoritmos/aho-corasick.MD"
description: "Algoritmo Aho-Corasick em Rust para busca simultanea de multiplos padroes em texto com automato baseado em Trie e links de falha."
date: "2026-02-24"
author: "Equipe Rust Brasil"
---

# Algoritmo Aho-Corasick em Rust

Algoritmo Aho-Corasick em Rust para busca simultanea de multiplos padroes em texto com automato baseado em Trie e links de falha.


O algoritmo de Aho-Corasick resolve um dos problemas mais importantes em processamento de texto: buscar **multiplos padroes simultaneamente** em um texto. Enquanto executar KMP ou Rabin-Karp para cada padrao individualmente custaria O(n*k) (onde `k` e o numero de padroes), o Aho-Corasick encontra todas as ocorrencias de todos os padroes em uma unica passagem pelo texto em O(n + m + z), onde `m` e a soma dos comprimentos dos padroes e `z` e o numero total de ocorrencias encontradas.

O algoritmo constroi um **automato finito** baseado em uma Trie dos padroes, equipado com dois tipos especiais de links: **links de falha** (para onde ir quando um caractere nao corresponde) e **links de dicionario** (para encontrar padroes que sao sufixos de outros). Criado por Alfred Aho e Margaret Corasick em 1975, e usado em ferramentas como `grep`, sistemas de deteccao de intrusao e filtros de conteudo.

## Como Funciona

### Fase 1: Construir a Trie

Primeiro inserimos todos os padroes em uma Trie normal:

```
Padroes: "he", "she", "his", "hers"

         (raiz)
        /     \
       h       s
      / \       \
     e*  i       h
     |   |       |
     r   s*      e*
     |
     s*

* = fim de padrao
```

### Fase 2: Construir Links de Falha (BFS)

Os links de falha conectam cada no ao no que representa o **maior sufixo proprio** que tambem e prefixo de algum padrao. Construimos via BFS (busca em largura):

```
                (raiz) <----+
               /     \      |
              h       s     |
             / \       \    |
   raiz <-- e*  i       h --+ (falha -> h da raiz)
            |   |       |
   raiz <-- r   s*      e* ---> e* (falha -> "he" e sufixo de "she"!)
            |                     (link de dicionario -> "he")
   raiz <-- s*

Links de falha (->):
  h -> raiz      (nenhum sufixo de "h" e prefixo)
  s -> raiz      (nenhum sufixo de "s" e prefixo)
  he -> raiz     (sufixo "e" nao e prefixo de padrao)
  hi -> raiz     (sufixo "i" nao e prefixo)
  sh -> h        ("h" e sufixo de "sh" E prefixo de "he","his")
  her -> raiz
  his -> s       ("s" e sufixo de "his" E prefixo de "she")
  she -> he      ("he" e sufixo de "she" E e um padrao!)
  hers -> s      ("s" e sufixo de "hers")
```

### Fase 3: Busca no Texto

Percorremos o texto caractere a caractere, seguindo a Trie. Em mismatch, seguimos o link de falha.

```
Texto: "ahishers"

Estado: raiz
  'a' -> nao tem filho 'a' -> fica na raiz
  'h' -> vai para no 'h'
  'i' -> vai para no 'hi'
  's' -> vai para no 'his' >>> MATCH: "his" na posicao 1 <<<
         link de falha -> 's' (no da Trie de "she")
  'h' -> de 's', vai para 'sh'
  'e' -> vai para 'she' >>> MATCH: "she" na posicao 3 <<<
         link de dicionario -> 'he' >>> MATCH: "he" na posicao 4 <<<
  'r' -> de 'she', falha -> 'he', filho 'r' -> 'her'
  's' -> vai para 'hers' >>> MATCH: "hers" na posicao 4 <<<

Resultado: "his"@1, "she"@3, "he"@4, "hers"@4
```

## Complexidade

| Fase                  | Tempo    | Espaco     |
|-----------------------|----------|------------|
| Construcao da Trie    | O(m)     | O(m*A)     |
| Links de falha (BFS)  | O(m*A)   | O(m)       |
| Busca no texto        | O(n+z)   | O(1)       |
| **Total**             |**O(m*A+n+z)**|**O(m*A)**|

Onde `m` = soma dos comprimentos dos padroes, `n` = comprimento do texto, `z` = numero de matches, `A` = tamanho do alfabeto. Na pratica, com HashMap para filhos, o fator `A` e substituido pelo numero medio de filhos por no.

## Implementacao em Rust

```rust
use std::collections::{HashMap, VecDeque};

/// Representa um no do automato Aho-Corasick.
#[derive(Debug)]
struct NoAC {
    filhos: HashMap<u8, usize>,    // byte -> indice do no filho
    link_falha: usize,              // indice do no de falha
    link_dicionario: Option<usize>, // proximo no que e fim de padrao (via falha)
    padrao_idx: Option<usize>,      // indice do padrao que termina aqui
    profundidade: usize,            // profundidade na Trie (= comprimento do prefixo)
}

impl NoAC {
    fn novo(profundidade: usize) -> Self {
        NoAC {
            filhos: HashMap::new(),
            link_falha: 0,
            link_dicionario: None,
            padrao_idx: None,
            profundidade,
        }
    }
}

/// Resultado de uma busca: posicao no texto e indice do padrao.
#[derive(Debug)]
struct Ocorrencia {
    posicao: usize,   // posicao inicial no texto
    padrao_idx: usize, // indice do padrao encontrado
}

/// Automato Aho-Corasick.
struct AhoCorasick {
    nos: Vec<NoAC>,
    padroes: Vec<String>,
}

impl AhoCorasick {
    /// Constroi o automato a partir de uma lista de padroes.
    fn construir(padroes: &[&str]) -> Self {
        let mut ac = AhoCorasick {
            nos: vec![NoAC::novo(0)], // no 0 = raiz
            padroes: padroes.iter().map(|s| s.to_string()).collect(),
        };

        // Fase 1: Inserir padroes na Trie
        for (idx, padrao) in padroes.iter().enumerate() {
            ac.inserir_padrao(padrao, idx);
        }

        // Fase 2: Construir links de falha e dicionario via BFS
        ac.construir_links();

        ac
    }

    /// Insere um padrao na Trie.
    fn inserir_padrao(&mut self, padrao: &str, idx: usize) {
        let mut no_atual = 0; // comeca na raiz

        for (profundidade, byte) in padrao.bytes().enumerate() {
            if !self.nos[no_atual].filhos.contains_key(&byte) {
                let novo_idx = self.nos.len();
                self.nos.push(NoAC::novo(profundidade + 1));
                self.nos[no_atual].filhos.insert(byte, novo_idx);
            }
            no_atual = self.nos[no_atual].filhos[&byte];
        }

        self.nos[no_atual].padrao_idx = Some(idx);
    }

    /// Constroi links de falha e links de dicionario usando BFS.
    fn construir_links(&mut self) {
        let mut fila: VecDeque<usize> = VecDeque::new();

        // Filhos diretos da raiz tem link de falha para a raiz
        let filhos_raiz: Vec<(u8, usize)> = self.nos[0].filhos.iter()
            .map(|(&b, &idx)| (b, idx))
            .collect();

        for &(_byte, filho_idx) in &filhos_raiz {
            self.nos[filho_idx].link_falha = 0;
            fila.push_back(filho_idx);
        }

        // BFS para construir links de falha
        while let Some(no_idx) = fila.pop_front() {
            let filhos: Vec<(u8, usize)> = self.nos[no_idx].filhos.iter()
                .map(|(&b, &idx)| (b, idx))
                .collect();

            for (byte, filho_idx) in filhos {
                // Encontra o link de falha para o filho
                let mut falha = self.nos[no_idx].link_falha;

                // Sobe pelos links de falha ate encontrar um no com filho 'byte'
                while falha != 0 && !self.nos[falha].filhos.contains_key(&byte) {
                    falha = self.nos[falha].link_falha;
                }

                let link_falha = if let Some(&destino) = self.nos[falha].filhos.get(&byte) {
                    if destino != filho_idx {
                        destino
                    } else {
                        0 // evita loop para si mesmo
                    }
                } else {
                    0 // volta para a raiz
                };

                self.nos[filho_idx].link_falha = link_falha;

                // Link de dicionario: proximo no que e fim de padrao via links de falha
                self.nos[filho_idx].link_dicionario =
                    if self.nos[link_falha].padrao_idx.is_some() {
                        Some(link_falha)
                    } else {
                        self.nos[link_falha].link_dicionario
                    };

                fila.push_back(filho_idx);
            }
        }
    }

    /// Busca todos os padroes no texto.
    fn buscar(&self, texto: &str) -> Vec<Ocorrencia> {
        let mut resultados = Vec::new();
        let mut estado = 0; // comeca na raiz

        for (i, byte) in texto.bytes().enumerate() {
            // Segue links de falha ate encontrar transicao valida
            while estado != 0 && !self.nos[estado].filhos.contains_key(&byte) {
                estado = self.nos[estado].link_falha;
            }

            if let Some(&proximo) = self.nos[estado].filhos.get(&byte) {
                estado = proximo;
            }
            // Se nenhuma transicao, fica na raiz (estado = 0)

            // Verifica se o estado atual e fim de padrao
            if let Some(idx) = self.nos[estado].padrao_idx {
                let pos = i + 1 - self.padroes[idx].len();
                resultados.push(Ocorrencia {
                    posicao: pos,
                    padrao_idx: idx,
                });
            }

            // Segue links de dicionario para encontrar padroes menores
            let mut dict_link = self.nos[estado].link_dicionario;
            while let Some(dict_no) = dict_link {
                if let Some(idx) = self.nos[dict_no].padrao_idx {
                    let pos = i + 1 - self.padroes[idx].len();
                    resultados.push(Ocorrencia {
                        posicao: pos,
                        padrao_idx: idx,
                    });
                }
                dict_link = self.nos[dict_no].link_dicionario;
            }
        }

        resultados
    }
}

fn main() {
    let padroes = vec!["he", "she", "his", "hers"];
    let texto = "ahishers";

    println!("Padroes: {:?}", padroes);
    println!("Texto:   \"{}\"", texto);
    println!();

    let ac = AhoCorasick::construir(&padroes);
    let resultados = ac.buscar(texto);

    println!("Ocorrencias encontradas:");
    for oc in &resultados {
        let padrao = &ac.padroes[oc.padrao_idx];
        println!(
            "  \"{}\" encontrado na posicao {} (texto[{}..{}])",
            padrao,
            oc.posicao,
            oc.posicao,
            oc.posicao + padrao.len()
        );
    }

    // Visualizacao no texto
    println!();
    println!("Visualizacao:");
    println!("  {}", texto);
    for oc in &resultados {
        let padrao = &ac.padroes[oc.padrao_idx];
        let espacos = " ".repeat(oc.posicao + 2);
        let sublinhado = "^".repeat(padrao.len());
        println!("{}{}  \"{}\"", espacos, sublinhado, padrao);
    }
}
```

## Exemplo de Execucao

```
Padroes: ["he", "she", "his", "hers"]
Texto:   "ahishers"

Ocorrencias encontradas:
  "his" encontrado na posicao 1 (texto[1..4])
  "she" encontrado na posicao 3 (texto[3..6])
  "he" encontrado na posicao 4 (texto[4..6])
  "hers" encontrado na posicao 4 (texto[4..8])

Visualizacao:
  ahishers
   ^^^      "his"
     ^^^    "she"
      ^^    "he"
      ^^^^  "hers"
```

Trace detalhado do automato:

```
Texto: a  h  i  s  h  e  r  s
       0  1  2  3  4  5  6  7

Estado apos cada caractere:
  'a' (i=0): raiz nao tem 'a' -> estado=raiz
  'h' (i=1): raiz tem 'h'     -> estado=h
  'i' (i=2): h tem 'i'        -> estado=hi
  's' (i=3): hi tem 's'       -> estado=his (MATCH "his"@1)
             falha(his) -> s   -> segue para verificar dicionario
  'h' (i=4): s tem 'h'        -> estado=sh
  'e' (i=5): sh tem 'e'       -> estado=she (MATCH "she"@3)
             dict(she) -> he   -> MATCH "he"@4
  'r' (i=6): she nao tem 'r'
             falha(she) -> he, he tem 'r' -> estado=her
  's' (i=7): her tem 's'      -> estado=hers (MATCH "hers"@4)
```

## Variacoes e Otimizacoes

### 1. Busca Case-Insensitive

```rust
/// Constroi o automato normalizando para minusculas.
fn construir_case_insensitive(padroes: &[&str]) -> AhoCorasick {
    let normalizados: Vec<String> = padroes.iter()
        .map(|p| p.to_lowercase())
        .collect();
    let refs: Vec<&str> = normalizados.iter().map(|s| s.as_str()).collect();
    AhoCorasick::construir(&refs)
}

/// Busca normalizando o texto para minusculas.
fn buscar_case_insensitive(ac: &AhoCorasick, texto: &str) -> Vec<Ocorrencia> {
    let texto_lower = texto.to_lowercase();
    ac.buscar(&texto_lower)
}
```

### 2. Filtro de Conteudo com Substituicao

```rust
/// Substitui todas as ocorrencias dos padroes por asteriscos.
fn censurar_texto(texto: &str, padroes: &[&str]) -> String {
    let ac = AhoCorasick::construir(padroes);
    let resultados = ac.buscar(texto);

    let mut chars: Vec<char> = texto.chars().collect();
    // Marca posicoes que devem ser censuradas
    let mut censurar = vec![false; chars.len()];

    for oc in &resultados {
        let padrao = &ac.padroes[oc.padrao_idx];
        for j in oc.posicao..oc.posicao + padrao.len() {
            if j < censurar.len() {
                censurar[j] = true;
            }
        }
    }

    for (i, deve_censurar) in censurar.iter().enumerate() {
        if *deve_censurar {
            chars[i] = '*';
        }
    }

    chars.into_iter().collect()
}

fn main() {
    let texto = "Este texto contem palavras proibidas como spam e virus";
    let proibidas = vec!["spam", "virus"];
    let censurado = censurar_texto(texto, &proibidas);
    println!("Original:  {}", texto);
    println!("Censurado: {}", censurado);
}
```

### 3. Contagem Eficiente de Padroes

```rust
/// Conta quantas vezes cada padrao aparece no texto.
fn contar_padroes(texto: &str, padroes: &[&str]) -> Vec<(String, usize)> {
    let ac = AhoCorasick::construir(padroes);
    let resultados = ac.buscar(texto);

    let mut contagens = vec![0usize; padroes.len()];
    for oc in &resultados {
        contagens[oc.padrao_idx] += 1;
    }

    padroes.iter()
        .enumerate()
        .map(|(i, &p)| (p.to_string(), contagens[i]))
        .filter(|(_, c)| *c > 0)
        .collect()
}
```

## Aplicacoes Praticas

### Sistema de Deteccao de Intrusao (IDS)

```rust
/// Simula um IDS simplificado que verifica pacotes de rede
/// contra assinaturas conhecidas de ataques.
fn verificar_pacote(payload: &str, assinaturas: &AhoCorasick) -> Vec<String> {
    let ocorrencias = assinaturas.buscar(payload);
    let mut alertas = Vec::new();

    for oc in &ocorrencias {
        let padrao = &assinaturas.padroes[oc.padrao_idx];
        alertas.push(format!(
            "ALERTA: Assinatura \"{}\" detectada na posicao {}",
            padrao, oc.posicao
        ));
    }

    alertas
}

fn main() {
    let assinaturas_ataque = vec![
        "DROP TABLE",
        "UNION SELECT",
        "<script>",
        "../../../",
        "cmd.exe",
    ];

    let ac = AhoCorasick::construir(&assinaturas_ataque);

    let pacotes = vec![
        "SELECT * FROM users WHERE id=1",
        "SELECT * FROM users UNION SELECT * FROM senhas",
        "GET /page?q=<script>alert(1)</script>",
        "GET /files/../../../etc/passwd",
    ];

    for pacote in &pacotes {
        let alertas = verificar_pacote(pacote, &ac);
        if alertas.is_empty() {
            println!("[OK] {}", pacote);
        } else {
            for alerta in &alertas {
                println!("{}", alerta);
            }
        }
        println!();
    }
}
```

### Extrator de Palavras-Chave para SEO

```rust
/// Extrai e conta palavras-chave relevantes em um texto.
fn analisar_palavras_chave(texto: &str, palavras_chave: &[&str]) -> Vec<(String, usize, f64)> {
    let texto_lower = texto.to_lowercase();
    let total_palavras = texto.split_whitespace().count();

    let ac = AhoCorasick::construir(palavras_chave);
    let resultados = ac.buscar(&texto_lower);

    let mut contagens = vec![0usize; palavras_chave.len()];
    for oc in &resultados {
        contagens[oc.padrao_idx] += 1;
    }

    let mut analise: Vec<(String, usize, f64)> = palavras_chave.iter()
        .enumerate()
        .filter(|(i, _)| contagens[*i] > 0)
        .map(|(i, &p)| {
            let densidade = (contagens[i] as f64 / total_palavras as f64) * 100.0;
            (p.to_string(), contagens[i], densidade)
        })
        .collect();

    analise.sort_by(|a, b| b.1.cmp(&a.1));
    analise
}
```

## Comparacao com Outros Algoritmos

| Algoritmo          | Padroes | Construcao  | Busca     | Espaco   |
|--------------------|---------|-------------|-----------|----------|
| KMP (por padrao)   | 1       | O(m)        | O(n)      | O(m)     |
| KMP (k padroes)    | k       | O(soma m)   | O(n*k)    | O(soma m)|
| Rabin-Karp multi   | k       | O(soma m)   | O(n*k)*   | O(k)     |
| **Aho-Corasick**   | **k**   |**O(m*A)**   |**O(n+z)** |**O(m*A)**|
| Regex (alternacao) | k       | O(soma m)   | O(n*soma m)| O(soma m)|

\* Caso medio. `m` = soma dos comprimentos, `A` = tamanho do alfabeto, `z` = ocorrencias.

O Aho-Corasick e o algoritmo ideal quando voce precisa buscar **muitos padroes simultaneamente**. O tempo de busca O(n+z) e independente do numero de padroes, o que o torna imbativel para aplicacoes como filtros de conteudo e IDS.

## Exercicios Praticos

1. **Busca com wildcards**: Estenda o Aho-Corasick para suportar o caractere '?' que corresponde a qualquer byte. Dica: ao encontrar '?', adicione transicoes para todos os bytes possiveis.

2. **Streaming**: Modifique a implementacao para processar texto em chunks (pedacos), mantendo o estado do automato entre chamadas. Isso e util para processar grandes arquivos sem carrega-los inteiramente em memoria.

3. **Padroes com prioridade**: Quando multiplos padroes se sobrepoem na mesma posicao, retorne apenas o mais longo (ou o de maior prioridade). Implemente uma versao que resolve conflitos.

4. **Visualizador de automato**: Crie uma funcao que imprime a estrutura do automato (nos, transicoes, links de falha) em formato legivel, como uma tabela.

## Veja Tambem

- [VecDeque na Biblioteca Padrao](/stdlib/vecdeque/) -- fila dupla usada no BFS
- [HashMap](/stdlib/hashmap/) -- mapa hash para transicoes dos nos
- [String em Rust](/stdlib/string/) -- manipulacao de strings
- [Vec: Vetores Dinamicos](/stdlib/vec/) -- armazenamento dos nos e resultados
- [Trie em Rust](/algoritmos/trie/) -- estrutura base do automato Aho-Corasick
- [Algoritmo KMP](/algoritmos/kmp/) -- busca de padrao unico