Algoritmo KMP e a Otimização da Função de Falha

A correspondência de padrões em strings é um problema fundamental na ciência da computação. O algoritmo Knuth-Morris-Pratt (KMP) resolve esse problema de forma eficiente para um único padrão, evitando retrocessos no texto principal. O núcleo do KMP reside na construção da função de falha (frequentemente denominada array next ou lps), que determina o comprimento do prefixo próprio mais longo que também é um sufixo.

Uma otimização crucial na construção dessa função visa eliminar comparações redundantes. Se o caractere atual do padrão for idêntico ao caractere na posição do prefixo correspondente, a transição de falha pode herdar diretamente o valor de falha do prefixo, pulando estados que inevitavelmente falhariam na correspondência.

#include <iostream>
#include <vector>
#include <string>

std::vector<int> buildFailureFunction(const std::string& pattern) {
    int m = pattern.size();
    std::vector<int> fail(m, -1);
    int j = -1;
    
    for (int i = 1; i < m; ++i) {
        while (j >= 0 && pattern[i - 1] != pattern[j]) {
            j = fail[j];
        }
        j++;
        
        // Otimização: evita transições redundantes no autômato
        // Se os caracteres forem iguais, herdamos o estado de falha do prefixo
        if (pattern[i] == pattern[j]) {
            fail[i] = fail[j];
        } else {
            fail[i] = j;
        }
    }
    return fail;
}

int searchPattern(const std::string& text, const std::string& pattern) {
    std::vector<int> fail = buildFailureFunction(pattern);
    int j = 0;
    
    for (int i = 0; i < text.size(); ++i) {
        while (j >= 0 && pattern[j] != text[i]) {
            j = fail[j];
        }
        j++;
        
        if (j == pattern.size()) {
            return i - j + 1; // Retorna o índice inicial da correspondência
        }
    }
    return -1;
}

int main() {
    std::cout << searchPattern("abababaab", "ababaa") << std::endl;
    std::cout << searchPattern("abababbba", "ababaa") << std::endl;
    return 0;
}

Autômato de Aho-Corasick para Múltiplos Padrões

Quando o objetivo é buscar múltiplos padrões simultaneamente, o autômato de Aho-Corasick é a estrutura de dados ideal. Ele combina a estrutura de Trie com ponteiros de falha (suffix links), permitindo que a máquina de estados transite eficientemente entre correspondências parciais de diferentes padrões.

A abordagem mais robusta e eficiente para construir os ponteiros de falha utiliza uma Busca em Largura (BFS). Além disso, é possível otimizar a fase de consulta pré-calculando a contagem total de correspondências acumuladas ao longo da cadeia de falha de cada nó, eliminando a necessidade de percorrer os ponteiros de falha recursivamente durante a busca no texto.

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>

struct TrieNode {
    std::unordered_map<char, int> children;
    int fail_link;
    int match_count; 
    bool is_end;

    TrieNode() : fail_link(0), match_count(0), is_end(false) {}
};

class AhoCorasickAutomaton {
private:
    std::vector<TrieNode> trie;

    void insertPattern(const std::string& word) {
        int curr = 0;
        for (char ch : word) {
            if (trie[curr].children.find(ch) == trie[curr].children.end()) {
                trie[curr].children[ch] = trie.size();
                trie.emplace_back();
            }
            curr = trie[curr].children[ch];
        }
        trie[curr].is_end = true;
        trie[curr].match_count++;
    }

public:
    AhoCorasickAutomaton() {
        trie.emplace_back(); // Nó raiz
    }

    void buildAutomaton(const std::vector<std::string>& patterns) {
        for (const auto& p : patterns) {
            insertPattern(p);
        }

        std::queue<int> q;
        
        // Inicializa os filhos diretos da raiz
        for (auto& pair : trie[0].children) {
            int child_idx = pair.second;
            trie[child_idx].fail_link = 0;
            q.push(child_idx);
        }

        // Construção dos ponteiros de falha via BFS
        while (!q.empty()) {
            int u = q.front();
            q.pop();

            // Otimização: acumula contagens de correspondência da cadeia de falha
            trie[u].match_count += trie[trie[u].fail_link].match_count;

            for (auto& pair : trie[u].children) {
                char ch = pair.first;
                int v = pair.second;
                
                int f = trie[u].fail_link;
                while (f != 0 && trie[f].children.find(ch) == trie[f].children.end()) {
                    f = trie[f].fail_link;
                }
                
                if (trie[f].children.find(ch) != trie[f].children.end() && trie[f].children[ch] != v) {
                    trie[v].fail_link = trie[f].children[ch];
                } else {
                    trie[v].fail_link = 0;
                }
                q.push(v);
            }
        }
    }

    int countMatches(const std::string& text) {
        int curr = 0;
        int total_matches = 0;
        
        for (char ch : text) {
            while (curr != 0 && trie[curr].children.find(ch) == trie[curr].children.end()) {
                curr = trie[curr].fail_link;
            }
            if (trie[curr].children.find(ch) != trie[curr].children.end()) {
                curr = trie[curr].children[ch];
            }
            // Adiciona diretamente as correspondências acumuladas
            total_matches += trie[curr].match_count;
        }
        return total_matches;
    }
};

int main() {
    std::vector<std::string> dict = {"he", "she", "his", "hers"};
    std::string text = "ahishers";
    
    AhoCorasickAutomaton ac;
    ac.buildAutomaton(dict);
    
    std::cout << "Total de ocorrências: " << ac.countMatches(text) << std::endl;
    return 0;
}