🌳 Algoritmo Aho-Corasick em PHP

O Aho-Corasick é como o KMP, mas com superpoderes. Enquanto o KMP busca uma palavra em um texto, o Aho-Corasick busca milhares de palavras simultaneamente, percorrendo o texto apenas uma vez.

É o algoritmo por trás de ferramentas como grep -F, sistemas de detecção de intrusão (IDS) e filtros de palavrões de alta performance.

💡 O Conceito: Trie + Fail Links

Imagine que queremos buscar as palavras: "HE", "SHE", "HERS", "HIS".

Em vez de comparar uma por uma, construímos uma Trie (Árvore de Prefixos) que funde essas palavras:

graph TD
    root((root)) --> H
    root --> S
    H --> E1(E*)
    H --> I
    I --> S1(S*)
    S --> H2(H)
    H2 --> E2(E*)
    E1 --> R
    R --> S2(S*)

    style E1 fill:#008f13,stroke:#333,stroke-width:2px
    style S1 fill:#008f13,stroke:#333,stroke-width:2px
    style E2 fill:#008f13,stroke:#333,stroke-width:2px
    style S2 fill:#008f13,stroke:#333,stroke-width:2px

(Nós marcados em verde indicam o fim de uma palavra)

O Pulo do Gato: Fail Links

Assim como no KMP, se falharmos no meio de um caminho (ex: lemos "SHE" e o próximo é "R", mas não temos "SHER"), não queremos voltar ao início. Queremos pular para o maior sufixo possível que também é um prefixo de outra palavra.

• Se falharmos em "SHE", podemos pular para "HE" (porque "HE" é sufixo de "SHE").
• Isso permite transitar entre os ramos da árvore sem nunca retroceder no texto.

🚀 Implementação em PHP

Vamos implementar um Filtro de Palavras-Chave eficiente.

<?php

class AhoCorasick {
    private $trie = [];
    private $fail = [];
    private $outputs = [];
    private $stateCount = 0;

    public function __construct() {
        $this->trie[0] = []; // Estado inicial (root)
    }

    /**
     * Adiciona uma palavra ao dicionário
     */
    public function addWord(string $word) {
        $state = 0;
        $len = strlen($word);
        for ($i = 0; $i < $len; $i++) {
            $char = $word[$i];
            if (!isset($this->trie[$state][$char])) {
                $this->stateCount++;
                $this->trie[$this->stateCount] = [];
                $this->trie[$state][$char] = $this->stateCount;
            }
            $state = $this->trie[$state][$char];
        }
        // Marca que este estado completa a palavra
        if (!isset($this->outputs[$state])) {
            $this->outputs[$state] = [];
        }
        $this->outputs[$state][] = $word;
    }

    /**
     * Constrói os Fail Links (BFS)
     */
    public function build() {
        $queue = [];

        // Inicializa profundidade 1 (filhos da raiz)
        foreach ($this->trie[0] as $char => $nextState) {
            $this->fail[$nextState] = 0;
            $queue[] = $nextState;
        }

        while (!empty($queue)) {
            $state = array_shift($queue);

            foreach ($this->trie[$state] as $char => $nextState) {
                // Configura fail link
                $f = $this->fail[$state];
                while ($f > 0 && !isset($this->trie[$f][$char])) {
                    $f = $this->fail[$f];
                }
                $this->fail[$nextState] = $this->trie[$f][$char] ?? 0;

                // Merge outputs (se "SHE" encontrou, "HE" também foi encontrado)
                if (isset($this->outputs[$this->fail[$nextState]])) {
                    if (!isset($this->outputs[$nextState])) $this->outputs[$nextState] = [];
                    $this->outputs[$nextState] = array_merge(
                        $this->outputs[$nextState],
                        $this->outputs[$this->fail[$nextState]]
                    );
                }

                $queue[] = $nextState;
            }
        }
    }

    /**
     * Busca todas as ocorrências no texto
     */
    public function search(string $text): array {
        $state = 0;
        $results = [];
        $len = strlen($text);

        for ($i = 0; $i < $len; $i++) {
            $char = $text[$i];
            while ($state > 0 && !isset($this->trie[$state][$char])) {
                $state = $this->fail[$state];
            }
            $state = $this->trie[$state][$char] ?? 0;

            if (isset($this->outputs[$state])) {
                foreach ($this->outputs[$state] as $word) {
                    $results[] = [
                        'word' => $word,
                        'position' => $i - strlen($word) + 1
                    ];
                }
            }
        }
        return $results;
    }
}

// --- Teste Prático: Filtro de Conteúdo ---

$ac = new AhoCorasick();
$ac->addWord("he");
$ac->addWord("she");
$ac->addWord("his");
$ac->addWord("hers");
$ac->build();

$texto = "ushers";
$encontrados = $ac->search($texto);

foreach ($encontrados as $match) {
    echo "Encontrado '{$match['word']}' na posição {$match['position']}\n";
}

// Saída esperada
// Encontrado 'she' na posição 1
// Encontrado 'he' na posição 2
// Encontrado 'hers' na posição 2

Note que em "ushers", ele encontrou "she", "he" e "hers". O algoritmo detecta sobreposições perfeitamente!

🎩 Trick: Substituição Simples

Se o seu objetivo NÃO é encontrar as posições ou lidar com sobreposições complexas, mas apenas substituir palavras (ex: trocar palavrões por ***), você não precisa implementar tudo isso.

O PHP tem uma função nativa super otimizada para isso:

👉 Substituição em Massa: O Poder do strtr()

⚠️ Considerações Finais

O Aho-Corasick é a escolha definitiva quando você tem um dicionário fixo e precisa varrer textos buscando qualquer ocorrência desse dicionário. Sua complexidade é linear em relação ao tamanho do texto $O(N)$, independentemente de quantas palavras existem no dicionário.