Autômato Aho-Corasick: Uma Visão Geral
O Autômato Aho-Corasick (AC) é um algoritmo eficiente para busca de múltiplos padrões em um texto. Ele se destaca por realizar essa tarefa em complexidade linear em relação ao tamanho total dos padrões e do texto. Essencialmente, se você possui um conjunto de cadeias de caracteres (padrões) e uma cadeia de caracteres maior (texto), o AC Automaton pode encontrar todas as ocorrências dos padrões no texto.
Para entender o Aho-Corasick, é útil ter conhecimento prévio de duas estruturas e algoritmos fundamentais:
- Trie (Árvore de Prefixos): Uma estrutura de dados em árvore utilizada para armazenar um conjunto de strings de forma que prefixos comuns possam ser compartilhados entre as strings.
- Algoritmo KMP (Knuth-Morris-Pratt): Um algoritmo de busca de padrões em strings que otimiza a verificação de prefixos em casos de falha de correspondência, evitando recuos desnecessários.
O Problema da Busca de Múltiplos Padrões
Considere o seguinte problema: dado \\(N\\) padrões de string \\(s_i\\) e um texto \\(T\\), determine quantos padrões distintos ocorrem no texto \\(T\\). Dois padrões são considerados distintos se seus índices originais forem diferentes.
As restrições comuns para esse tipo de probleam incluem: \\(1 \leq N \leq 10^6\\), \\(1 \leq |T| \leq 10^6\\), e \\(1 \leq \sum\limits_{i = 1}^N |s_i| \leq 10^6\\). Todas as strings geralmente contêm apenas letras minúsculas.
A abordagem ingênua de aplicar o KMP individualmente para cada padrão resultaria em uma complexidade quadrática, o que é inaceitável para as restrições dadas. O Aho-Corasick resolve isso combinando as forças do Trie e do KMP. Ele constrói uma Trie a partir de todos os padrões e, em seguida, estende essa Trie com "links de falha" (fail links), análogos à função de prefixo-sufixo do KMP, permitindo uma busca linear.
Links de Falha (Fail Links)
No KMP, a função de falha (comumente chamada de \\(f\\) ou \\(next\\) array) indica para onde o ponteiro do padrão deve retroceder se ocorrer uma falha de correspondência. Em termos mais formais, \\(f[i]\\) é o comprimento do maior prefixo de \\(S\\) que também é um sufixo próprio de \\(S[0 \dots i-1]\\).
O conceito de links de falha no Aho-Corasick é uma generalização disso para a estrutura Trie. Para qualquer nó \\(u\\) na Trie, seu link de falha \\(f[u]\\) aponta para o nó \\(v\\) tal que a string representada pelo caminho da raiz até \\(v\\) é o sufixo mais longo do caminho da raiz até \\(u\\) que também é um prefixo de algum padrão. Em outras palavras, se uma correspondência falha no nó \\(u\\), podemos pular para \\(f[u]\\) e tentar continuar a correspondência a partir daí, garantindo que mantemos o maior sufixo possível que pode ainda formar um prefixo de um padrão.
Imagine um Trie construído com os padrões "she", "he", "say", "shr", "her". Se você está no nó que representa "sh" e o próximo caractere não corresponde a 'e' ou 'r', você usaria o link de falha para retroceder. O link de falha do nó "sh" levaria ao nó "h" (pois "h" é o sufixo próprio mais longo de "sh" que também é prefixo de um padrão). A partir de "h", você tentaria a correspondência para o próximo caractere.
Construção do Autômato Aho-Corasick
A construção do autômato envolve três etapas principais:
1. Inserção de Padrões na Trie
Esta etapa é idêntica à construção de uma Trie padrão. Cada padrão é inserido, e cada nó na Trie representa um prefixo de um ou mais padrões. Um contador ou flag em cada nó pode indicar se um ou mais padrões terminam naquele nó.
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <array>
const int ALPHABET_SIZE = 26;
const int MAX_NODES = 1000005; // Máximo de 10^6 + 5 nós
// Representa a Trie: trie_nodes[id_do_no][indice_do_caractere] -> proximo_id_do_no
std::array<std::array<int, ALPHABET_SIZE>, MAX_NODES> trie_nodes;
// Conta quantos padrões terminam em um determinado nó
std::array<int, MAX_NODES> pattern_end_counts;
// failure_links[id_do_no] -> id_do_no do link de falha
std::array<int, MAX_NODES> failure_links;
int node_counter = 0; // Contador global de nós, começa em 0 para a raiz
// Função para inserir um padrão na Trie
void insert_pattern(const std::string& pattern) {
int current_node = 0; // Começa na raiz (nó 0)
for (char character : pattern) {
int char_index = character - 'a'; // 'a' -> 0, 'b' -> 1, ...
if (trie_nodes[current_node][char_index] == 0) {
// Se não houver um nó para este caractere, crie um novo
trie_nodes[current_node][char_index] = ++node_counter;
}
current_node = trie_nodes[current_node][char_index]; // Move para o próximo nó
}
pattern_end_counts[current_node]++; // Incrementa o contador de padrões que terminam neste nó
}
2. Construção dos Links de Falha (Função build)
Os links de falha são construídos usando uma busca em largura (BFS). A ideia é que o link de falha de um nó \\(u\\) que representa a string \\(S_u\\) aponta para o nó que representa o maior sufixo próprio de \\(S_u\\) que também é um prefixo de algum padrão. Os nós de nível 1 (filhos da raiz) têm seus links de falha apontando para a raiz.
Para um nó \\(u\\) e seu filho \\(v\\) (alcançado pelo caractere \\(c\\)), o link de falha de \\(v\\) pode ser encontrado seguindo o link de falha de \\(u\\) até \\(f[u]\\), e então tentando seguir o caractere \\(c\\) a partir de \\(f[u]\\). Este processo é análogo à construção da tabela KMP, mas em uma estrutura de árvore.
Uma otimização importante, conhecida como "trie graph", elimina a necessidade de um while loop durante a travessia. Se um nó \\(u\\) não tem um filho para o caractere \\(c\\), ele pode ser otimizado para apontar diretamante para o filho de seu link de falha \\(f[u]\\) para o caractere \\(c\\). Isso garante que cada passo no texto leva a um novo nó em tempo constante.
// Função para construir os links de falha (fail links) usando BFS
void build_failure_links() {
std::queue<int> q;
// Inicializa os links de falha para os filhos da raiz.
// Seus links de falha apontam para a raiz (nó 0).
for (int i = 0; i < ALPHABET_SIZE; ++i) {
if (trie_nodes[0][i] != 0) {
// Adiciona filhos da raiz à fila
q.push(trie_nodes[0][i]);
}
}
while (!q.empty()) {
int current_node = q.front();
q.pop();
for (int i = 0; i < ALPHABET_SIZE; ++i) {
int child_node = trie_nodes[current_node][i]; // O filho direto de current_node para o caractere 'i'
int fail_node_of_parent = failure_links[current_node]; // O link de falha do nó pai
if (child_node == 0) {
// Se o nó atual não tem um filho direto para o caractere 'i',
// ele "herda" o caminho do seu link de falha.
// Isso cria o "trie graph" otimizado, evitando recuos explícitos.
trie_nodes[current_node][i] = trie_nodes[fail_node_of_parent][i];
} else {
// Se existe um filho direto, define seu link de falha.
// O link de falha de child_node é o nó alcançado seguindo o link de falha
// do pai e depois o mesmo caractere 'i'.
failure_links[child_node] = trie_nodes[fail_node_of_parent][i];
q.push(child_node); // Adiciona o filho à fila para processamento posterior
}
}
}
}
3. Consulta (Função query)
Para encontrar os padrões no texto, percorremos o texto caractere por caractere. Em cada caractere do texto, tentamos avançar na Trie. Se não houver uma transição direta para o caractere atual, o "trie graph" otimizado nos direcionará automaticamente através dos links de falha até encontrarmos uma transição válida (ou a raiz). Uma vez que chegamos a um nó, precisamos contar não apenas os padrões que terminam exatamente naquele nó, mas também os padrões que terminam nos nós alcançados por seus links de falha (pois esses representam sufixos do prefixo atual que também são padrões). Para evitar a contagem duplicada de padrões, marcamos os nós como "já contados" (por exemplo, definindo pattern_end_counts[node] = -1).
// Função para consultar ocorrências de padrões em um texto
int count_pattern_occurrences(const std::string& text) {
int current_node = 0;
int total_found_patterns = 0;
for (char character : text) {
int char_index = character - 'a';
// Percorre o trie graph. A otimização em build_failure_links garante
// que trie_nodes[current_node][char_index] sempre fornece um nó válido
// (direto ou via link de falha).
current_node = trie_nodes[current_node][char_index];
int temp_node = current_node;
// Percorre os links de falha a partir do nó atual para contar todos os padrões
// que terminam no prefixo atual ou em seus sufixos.
while (temp_node != 0 && pattern_end_counts[temp_node] != -1) {
total_found_patterns += pattern_end_counts[temp_node];
pattern_end_counts[temp_node] = -1; // Marca como contado para evitar re-contagem
temp_node = failure_links[temp_node]; // Move para o link de falha
}
}
return total_found_patterns;
}
Código Completo
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <array>
const int ALPHABET_SIZE = 26;
const int MAX_NODES = 1000005; // Máximo de 10^6 + 5 nós
std::array<std::array<int, ALPHABET_SIZE>, MAX_NODES> trie_nodes; // trie_nodes[id_do_no][indice_do_caractere] -> proximo_id_do_no
std::array<int, MAX_NODES> pattern_end_counts; // pattern_end_counts[id_do_no] -> count de padrões que terminam aqui
std::array<int, MAX_NODES> failure_links; // failure_links[id_do_no] -> id_do_no para link de falha
int node_counter = 0; // Contador global de nós, começa em 0 para a raiz
// Função para inserir um padrão na Trie
void insert_pattern(const std::string& pattern) {
int current_node = 0; // Começa na raiz (nó 0)
for (char character : pattern) {
int char_index = character - 'a';
if (trie_nodes[current_node][char_index] == 0) {
trie_nodes[current_node][char_index] = ++node_counter;
}
current_node = trie_nodes[current_node][char_index];
}
pattern_end_counts[current_node]++; // Marca que um padrão termina neste nó
}
// Função para construir os links de falha (fail links) usando BFS
void build_failure_links() {
std::queue<int> q;
// Inicializa os links de falha para os filhos da raiz.
// Seus links de falha apontam para a raiz (nó 0).
for (int i = 0; i < ALPHABET_SIZE; ++i) {
if (trie_nodes[0][i] != 0) {
q.push(trie_nodes[0][i]);
}
}
while (!q.empty()) {
int current_node = q.front();
q.pop();
for (int i = 0; i < ALPHABET_SIZE; ++i) {
int child_node = trie_nodes[current_node][i];
int fail_node_of_parent = failure_links[current_node];
if (child_node == 0) {
// Otimização do trie graph: se não há filho direto, use o caminho do link de falha do pai.
trie_nodes[current_node][i] = trie_nodes[fail_node_of_parent][i];
} else {
// Define o link de falha do filho.
failure_links[child_node] = trie_nodes[fail_node_of_parent][i];
q.push(child_node);
}
}
}
}
// Função para consultar ocorrências de padrões em um texto
int count_pattern_occurrences(const std::string& text) {
int current_node = 0;
int total_found_patterns = 0;
for (char character : text) {
int char_index = character - 'a';
current_node = trie_nodes[current_node][char_index]; // Percorre o trie graph
int temp_node = current_node;
// Percorre os links de falha para contar padrões.
while (temp_node != 0 && pattern_end_counts[temp_node] != -1) {
total_found_patterns += pattern_end_counts[temp_node];
pattern_end_counts[temp_node] = -1; // Marca como contado
temp_node = failure_links[temp_node];
}
}
return total_found_patterns;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int num_patterns;
std::cin >> num_patterns;
for (int i = 0; i < num_patterns; ++i) {
std::string s_pattern;
std::cin >> s_pattern;
insert_pattern(s_pattern);
}
build_failure_links();
std::string text_to_search;
std::cin >> text_to_search;
std::cout <> count_pattern_occurrences(text_to_search) << std::endl;
return 0;
}