Tópicos Extras: Strings e Autômatos de Busca

Metáfora e Motivação

Quando buscamos a palavra “P I P O C A” dentro de um livro imenso do tamanho da Wikipédia (“O P I P O P I P O C A C O L A …”), a força bruta ingênua tentará bater letra por letra \(N \times M\) vezes. Ao falhar na letra A de Pipoc[A] (porque ali apareceu P I P O C [I]), o algoritmo estúpido zera a busca e reconecta lááá atrás.

É aí que brilham os cérebros de Knuth-Morris-Pratt (KMP).

KMP e a Tabela LPS (Longest Prefix Suffix)

Ao errar a última letra \(A\) (“Pipoci…”), KMP não joga fora as 5 letras que deram trabalho para validar antes do erro! O algoritmo possui uma tabela mágica embutida batizada de \(\pi\) (Pi) ou LPS. Essa tabela joga nossa agulha confiançuda cirurgicamente na posição em que ela “poderia formar uma nova silaba” num \(\mathcal{O}(N+M)\).

Nesse exato compasso, existe a Compressão de Huffman (Uma árvore gulosa que destila Strings em chaves binárias enxutas baseadas na raridade dos caracteres), fundando a base das compressões de pacote ZIP e Mídias digitais!

Algoritmo OOP de Busca Limpa KMP (C++)

Seja para achar vírus injetados, ou genes na fita DNA com milhões de bytes, a varredura linear C++ nos atende:

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

using namespace std;

// Funcao pre-processadora que prepara o Padrão "P I P O C A" ensinando-o Onde pular caso falhe num degrau!
vector<int> montarPi(const string& P) {
    int m = P.size();
    vector<int> pi(m, 0); // Todo mundo lizo = salto 0 pra raiz global

    for (int i = 1, topoPrefixo = 0; i < m; i++) {
        // Enfiou o pe na jaca. Volto ate achar o match historico ou raiz 0
        while (topoPrefixo > 0 && P[i] != P[topoPrefixo]) {
            topoPrefixo = pi[topoPrefixo - 1]; 
        }

        // Deu Match na cabeca com meu sulfixo atual! Aumenta a engrenagem!
        if (P[i] == P[topoPrefixo]) {
            topoPrefixo++;
        }
        
        pi[i] = topoPrefixo;
    }
    return pi;
}

int kmb_busca_simples(const string& Texto, const string& Padrao) {
    if(Padrao.empty()) return 0;
    
    vector<int> pi = montarPi(Padrao);
    int ocorrencias = 0;

    for (int i = 0, combinacoesCorrentes = 0; i < Texto.size(); i++) {
        // Leu letra errada no DNA. Volta na roda do LPS do padrao sem zerar o (i) principal do texto
        while (combinacoesCorrentes > 0 && Texto[i] != Padrao[combinacoesCorrentes]) {
            combinacoesCorrentes = pi[combinacoesCorrentes - 1];
        }

        if (Texto[i] == Padrao[combinacoesCorrentes]) {
            combinacoesCorrentes++;
        }

        // Placar CHEIO! A palavra toda bateu no molde! Contagem Aprovada!
        if (combinacoesCorrentes == Padrao.size()) {
            ocorrencias++;
            // Continua pulando ciente que consumiu a plalavra
            combinacoesCorrentes = pi[combinacoesCorrentes - 1]; 
        }
    }
    return ocorrencias;
}

void executando_testes() {
    string dicio = "PIPOCA DE BANANA E OUTRA PIPOCA OU PIPOCADEIRAS PIPO";
    
    // Tem que aparecer a PIPOCA limpa nas ocorrencias:
    // "PIPOCA DE BANANA E OUTRA PIPOCA OU PIPOCADEIRAS PIPO" -> Três Palavras PIPOCA localizadas
    assert(kmb_busca_simples(dicio, "PIPOCA") == 3);
    
    // Cadeia complexa KMP Skipping
    assert(kmb_busca_simples("ABABDABACDABABCABAB", "ABABCABAB") == 1);
    
    cout << "[✅] Testes do Motor Automato Limitante (KMP) de Strings Passados!\n";
}

int main() {
    executando_testes();
    return 0;
}

O C++ fornece na biblioteca moderna a string::find(). Contudo, é provado que contra autores sarcásticos de maratona que constroem strings como (AAAA…AAAAAB), o string::find() cai num perigosíssimo \(\mathcal{O}(NM)\) e causa Time-Limit no Beecrowd!

Problema Clássico

Problema: Link Bolado (Busca de Padrão) Link: Beecrowd 2651

Solução: Encontrar com flexibilização de UpperCase o exato Match da string zelda (Tudo Minúsculo, converta a macro do sistema inteiro!). Use o esqueleto matemático do código testado do KMP para injetar o array de matches sem jamais regredir o laço leitor \(I\).

Variações e Maratonas Extremas

[Cifra de César]
- Foco: Rotações na base ASCII. Subtração de char.
- Link: Beecrowd 1253
[Alienígenas e Assinaturas]
- Foco: Busca insana por cadeias gigantescas de DNA iguais sob múltiplos gabaritos. O motor da Google atua nisso com maestria batizado de Rolling Hash (ou algoritmo mágico Karp-Rabin)! Ele comprime a macro “ZELDA” e “MARIO” num número gigante primo, para realizar match em tempo linear numérico!
[De Dentro para Fora]
- Foco: Refino manual espelhado de ponteiros.
- Link: Beecrowd 1235