🔍 Algoritmo Rabin-Karp em PHP

O Rabin-Karp é um algoritmo de busca de string que utiliza hashing para encontrar padrões dentro de um texto. Diferente da busca força bruta, que compara caractere por caractere, o Rabin-Karp compara o hash do padrão com o hash de trechos do texto, tornando a verificação inicial muito mais rápida.

💡 Por que e Quando Usar?

O Rabin-Karp é aplicado em cenários onde a velocidade e a eficiência na análise de grandes volumes de texto são cruciais, especialmente quando envolvem múltiplas buscas ou verificação de integridade.

Embora o PHP forneça funções nativas otimizadas para busca de string (como strpos()), a aplicabilidade do Rabin-Karp em projetos PHP de grande escala reside em contextos muito específicos:

💻 1. Aplicabilidade em Ferramentas e Processamento de Dados

Análise de Logs e Parsing de Arquivos Grandes

Cenário: Processar arquivos de log de servidor (gigabytes de texto) ou arquivos de dados grandes (CSV, XML, etc.) para buscar padrões de erro, endereços IP ou sequências específicas. Vantagem do RK: Usar uma implementação otimizada do RK pode ser significativamente mais rápido do que a busca naive em laços, garantindo uma complexidade de tempo de $O(N+M)$ (linear) em média.

Compiladores, Parsers e Linguagens de Template

Cenário: Ferramentas que precisam identificar tokens (palavras-chave, variáveis, operadores) dentro de um código-fonte ou template. Vantagem do RK: É excelente para identificar múltiplos padrões simultaneamente (busca de múltiplos padrões), pois podemos armazenar os hashes dos padrões em um conjunto e verificar cada janela do texto contra esse conjunto.

🛡️ 2. Aplicações de Segurança e Integridade de Dados

O Rabin-Karp é particularmente poderoso devido à sua técnica de hashing rolante.

Detecção de Plágio e Similaridade

Cenário: Comparar grandes blocos de texto (documentos, códigos-fonte) para identificar seções que foram copiadas. Vantagem do RK: O hashing rolante permite comparar rapidamente os hashes de janelas de texto de tamanho fixo em diferentes documentos. Se os hashes coincidirem, é provável que o texto seja idêntico. Isso acelera enormemente o processo de detecção de similaridade.

Assinaturas Digitais e Verificação de Integridade de Arquivos

Cenário: Usar o hashing de string para gerar identificadores rápidos e únicos para partes de um arquivo. Vantagem do RK: A técnica de hashing rolante pode ser adaptada para gerar fingerprints (impressões digitais) rápidos de diferentes seções de um arquivo, permitindo verificar integridade sem reprocessar todo o arquivo a cada mudança mínima.

🚀 Implementação em PHP

Abaixo, uma implementação robusta do algoritmo Rabin-Karp utilizando Rolling Hash. Esta técnica permite recalcular o hash da próxima janela de texto em tempo constante $O(1)$, aproveitando o cálculo da janela anterior.

<?php

class RabinKarp {
    private $prime = 101; // Um número primo para o hash
    private $d = 256;     // Número de caracteres no alfabeto de entrada

    /**
     * Busca todas as ocorrências de um padrão em um texto.
     *
     * @param string $pattern O padrão a ser buscado
     * @param string $text O texto onde buscar
     * @return array Lista de índices onde o padrão foi encontrado
     */
    public function search(string $pattern, string $text): array {
        $m = strlen($pattern);
        $n = strlen($text);
        $i = 0;
        $j = 0;
        $p = 0; // Hash do padrão
        $t = 0; // Hash do texto
        $h = 1;
        $occurrences = [];

        if ($m > $n) return [];

        // O valor de h seria "pow(d, m-1) % prime"
        for ($i = 0; $i < $m - 1; $i++) {
            $h = ($h * $this->d) % $this->prime;
        }

        // Calcula o hash inicial do padrão e da primeira janela do texto
        for ($i = 0; $i < $m; $i++) {
            $p = ($this->d * $p + ord($pattern[$i])) % $this->prime;
            $t = ($this->d * $t + ord($text[$i])) % $this->prime;
        }

        // Desliza o padrão sobre o texto
        for ($i = 0; $i <= $n - $m; $i++) {
            // Se os hashes batem, verifica os caracteres um a um
            if ($p == $t) {
                $match = true;
                for ($j = 0; $j < $m; $j++) {
                    if ($text[$i + $j] != $pattern[$j]) {
                        $match = false;
                        break;
                    }
                }
                if ($match) {
                    $occurrences[] = $i;
                }
            }

            // Calcula o hash da próxima janela de texto:
            // Remove o dígito líder, adiciona o dígito final
            if ($i < $n - $m) {
                $t = ($this->d * ($t - ord($text[$i]) * $h) + ord($text[$i + $m])) % $this->prime;

                // Se obtivermos um valor negativo, convertemos para positivo
                if ($t < 0) {
                    $t = ($t + $this->prime);
                }
            }
        }

        return $occurrences;
    }
}

// --- Testes e Exemplos ---

$rk = new RabinKarp();

// Exemplo 1: Busca simples
$texto = "ABABDABACDABABCABAB";
$padrao = "ABABCABAB";
$resultado = $rk->search($padrao, $texto);
echo "Padrão encontrado nos índices: " . implode(", ", $resultado) . "\n";

// Exemplo 2: Múltiplas ocorrências
$texto2 = "AABAACAADAABAABA";
$padrao2 = "AABA";
$resultado2 = $rk->search($padrao2, $texto2);
echo "Ocorrências de 'AABA': " . implode(", ", $resultado2) . "\n";

// Saída esperada
// Padrão encontrado nos índices: 10
// Ocorrências de 'AABA': 0, 9, 12

🧠 Entendendo o Rolling Hash (O Pulo do Gato)

O segredo da performance está na atualização do hash. Em vez de recalcular tudo do zero para cada nova janela (o que seria lento), nós "deslizamos" a janela.

Imagine que estamos calculando o hash de números para simplificar. Texto: 1 2 3 4 5 Janela (tamanho 3): [1 2 3]

1. Hash Inicial: $1 \times 100 + 2 \times 10 + 3 \times 1 = 123$
2. Deslizar para direita: Sai o 1, entra o 4. Nova janela: [2 3 4]
3. Cálculo Rápido:
   • Pegamos o 123.
   • Removemos o 1 (o dígito mais à esquerda): $123 - (1 \times 100) = 23$.
   • Deslocamos para a esquerda (multiplicamos pela base): $23 \times 10 = 230$.
   • Adicionamos o 4 (o novo dígito): $230 + 4 = 234$.

Pronto! Calculamos o hash da nova janela 234 sem ter que iterar por todos os itens novamente.

Fórmula simplificada: $$ H{prox} = (H{atual} - \text{val}(char{sai}) \times h) \times d + \text{val}(char{entra}) \pmod q $$

🕵️ Exemplo Prático: Detector de Plágio (Similaridade)

Vamos sair da teoria e ir para um caso real. Imagine que você tem dois textos e quer saber se eles compartilham sentenças comuns. O Rabin-Karp é perfeito para isso porque podemos gerar hashes de todas as frases de um texto e verificar rapidamente se existem no outro.

<?php

class PlagiarismDetector {
    private $prime = 101;
    private $d = 256;

    /**
     * Verifica a porcentagem de similaridade baseada em subsequências comuns.
     * 
     * @param string $original Texto original
     * @param string $suspect Texto suspeito
     * @param int $windowSize Tamanho da janela de comparação (em caracteres)
     * @return float Porcentagem de similaridade (0 a 100)
     */
    public function checkSimilarity(string $original, string $suspect, int $windowSize = 10): float {
        $n = strlen($original);
        $m = strlen($suspect);

        if ($n < $windowSize || $m < $windowSize) return 0.0;

        // 1. Mapear todos os hashes de janelas do texto original
        $originalHashes = [];
        $h = 1; 
        $t = 0; // Hash atual

        // Pré-calcula h = pow(d, windowSize-1) % prime
        for ($i = 0; $i < $windowSize - 1; $i++) {
            $h = ($h * $this->d) % $this->prime;
        }

        // Calcula hash da primeira janela do original
        for ($i = 0; $i < $windowSize; $i++) {
            $t = ($this->d * $t + ord($original[$i])) % $this->prime;
        }
        $originalHashes[$t] = true; // Armazena o hash

        // Calcula o restante dos hashes do original (Rolling Hash)
        for ($i = 0; $i < $n - $windowSize; $i++) {
            $t = ($this->d * ($t - ord($original[$i]) * $h) + ord($original[$i + $windowSize])) % $this->prime;
            if ($t < 0) $t += $this->prime;
            $originalHashes[$t] = true;
        }

        // 2. Verificar quantas janelas do texto suspeito coincidem
        $matches = 0;
        $totalWindows = $m - $windowSize + 1;
        $p = 0;

        // Hash da primeira janela do suspeito
        for ($i = 0; $i < $windowSize; $i++) {
            $p = ($this->d * $p + ord($suspect[$i])) % $this->prime;
        }
        if (isset($originalHashes[$p])) $matches++;

        // Rolling hash no suspeito
        for ($i = 0; $i < $m - $windowSize; $i++) {
            $p = ($this->d * ($p - ord($suspect[$i]) * $h) + ord($suspect[$i + $windowSize])) % $this->prime;
            if ($p < 0) $p += $this->prime;

            if (isset($originalHashes[$p])) {
                $matches++;
            }
        }

        return ($matches / $totalWindows) * 100;
    }
}

// --- Teste Prático ---

$detector = new PlagiarismDetector();

$textoOriginal = "O rato roeu a roupa do rei de Roma e a rainha riu.";
$textoSuspeito = "Sabemos que o rato roeu a roupa do rei de Roma ontem.";

// Vamos usar uma janela de 10 caracteres para considerar "cópia"
$similaridade = $detector->checkSimilarity($textoOriginal, $textoSuspeito, 10);

echo "Similaridade detectada: " . round($similaridade, 2) . "%\n";

// Saída esperada
// Similaridade detectada: 72.73%

Nota: Em um sistema real de produção, você usaria um hash mais forte (como polinomial com módulo $10^9 + 7$) para evitar colisões, mas a lógica permanece idêntica.

🎩 Trick: Fingerprinting de Arquivos

Para ver como aplicar conceitos de hashing para detecção eficiente de mudanças em arquivos (similar ao rsync), confira nosso trick dedicado:

👉 Fingerprinting de Arquivos com Hashing em PHP

⚠️ Considerações Finais

A maior aplicabilidade no mundo real não é substituir as funções nativas como strpos, mas sim entender a lógica por trás delas para criar soluções customizadas de busca, diff e análise de dados.

Para ensino, o Rabin-Karp é excelente para demonstrar como alcançar complexidade $O(N+M)$ na prática através de hashing, elevando o nível de compreensão sobre algoritmos de texto.