Algoritmo Rabin-Karp em Rust

O algoritmo Rabin-Karp resolve o problema de busca de padroes em texto usando uma abordagem baseada em hashing. Em vez de comparar caractere por caractere, ele calcula um hash da janela atual do texto e compara com o hash do padrao. Quando os hashes coincidem, faz a verificacao caractere a caractere para confirmar (evitando falsos positivos por colisao).

A grande vantagem do Rabin-Karp sobre algoritmos como KMP e Boyer-Moore e sua capacidade natural de buscar multiplos padroes simultaneamente sem aumento significativo de complexidade. O segredo esta no uso de rolling hash (hash deslizante): ao mover a janela um caractere para a direita, o novo hash e calculado em O(1) a partir do hash anterior, sem precisar reprocessar todos os caracteres da janela.

Como Funciona

Hash Polinomial

Usamos um hash polinomial onde cada caractere contribui com seu valor multiplicado por uma potencia da base:

hash("ABC") = A * base^2 + B * base^1 + C * base^0  (mod primo)

Com base=256, primo=101:
hash("ABC") = 65*256^2 + 66*256 + 67 = 4259907 mod 101 = 15

Rolling Hash (Hash Deslizante)

Ao deslizar a janela de um caractere, removemos a contribuicao do caractere que sai e adicionamos o novo:

Texto:  [A B C] D E F     hash_janela = hash("ABC")
Texto:   A [B C D] E F    hash_janela = (hash_janela - A*base^(m-1)) * base + D

Visualizacao do calculo:

  hash("ABC") = A*base^2 + B*base^1 + C*base^0

  Para obter hash("BCD"):
  1. Remove A:  hash - A*base^2  =  B*base^1 + C*base^0
  2. Multiplica por base:         =  B*base^2 + C*base^1
  3. Adiciona D:                  =  B*base^2 + C*base^1 + D*base^0
                                  =  hash("BCD")  <<<

Processo Completo de Busca

Texto:   R U S T L A N G
         0 1 2 3 4 5 6 7

Padrao:  L A N   (m=3)

hash_padrao = hash("LAN") = 76*256^2 + 65*256 + 78 = 4997454 mod 101 = 62

Janela 0: "RUS"  hash = hash("RUS") mod 101 = ?  != 62  -> pula
Janela 1: "UST"  hash = rolling_hash       = ?  != 62  -> pula
Janela 2: "STL"  hash = rolling_hash       = ?  != 62  -> pula
Janela 3: "TLA"  hash = rolling_hash       = ?  != 62  -> pula
Janela 4: "LAN"  hash = rolling_hash       = 62 == 62  -> verifica!
          L==L, A==A, N==N -> MATCH na posicao 4!
Janela 5: "ANG"  hash = rolling_hash       = ?  != 62  -> pula

Resultado: padrao encontrado na posicao 4.

Complexidade

Caso	Tempo	Espaco
Melhor	O(n+m)	O(1)
Medio	O(n+m)	O(1)
Pior	O(n*m)	O(1)

O pior caso O(nm) ocorre quando todos os hashes colidem (todos falsos positivos), forcando verificacao completa a cada posicao. Na pratica, com bom primo e base, colisoes sao raras e o algoritmo opera em O(n+m). Para busca de k padroes, a complexidade media e O(nk + soma_m), pois calculamos k hashes de padrao e comparamos a cada posicao.

Implementacao em Rust

/// Constantes para o hash polinomial
const BASE: u64 = 256;
const PRIMO: u64 = 1_000_000_007; // primo grande para reduzir colisoes

/// Calcula (base^exp) mod primo de forma eficiente.
fn potencia_modular(base: u64, exp: u64, modulo: u64) -> u64 {
    let mut resultado: u64 = 1;
    let mut base = base % modulo;
    let mut exp = exp;

    while exp > 0 {
        if exp % 2 == 1 {
            resultado = resultado.wrapping_mul(base) % modulo;
        }
        exp /= 2;
        base = base.wrapping_mul(base) % modulo;
    }

    resultado
}

/// Busca todas as ocorrencias do padrao no texto usando Rabin-Karp.
fn rabin_karp_busca(texto: &str, padrao: &str) -> Vec<usize> {
    let texto = texto.as_bytes();
    let padrao = padrao.as_bytes();
    let n = texto.len();
    let m = padrao.len();

    if m == 0 || m > n {
        return Vec::new();
    }

    let mut ocorrencias = Vec::new();

    // Calcula base^(m-1) mod primo (para remover o caractere mais a esquerda)
    let h = potencia_modular(BASE, (m - 1) as u64, PRIMO);

    // Calcula hash inicial do padrao e da primeira janela do texto
    let mut hash_padrao: u64 = 0;
    let mut hash_janela: u64 = 0;

    for i in 0..m {
        hash_padrao = (hash_padrao.wrapping_mul(BASE) + padrao[i] as u64) % PRIMO;
        hash_janela = (hash_janela.wrapping_mul(BASE) + texto[i] as u64) % PRIMO;
    }

    // Desliza a janela pelo texto
    for i in 0..=(n - m) {
        // Se os hashes coincidem, verifica caractere a caractere
        if hash_padrao == hash_janela {
            if texto[i..i + m] == padrao[..] {
                ocorrencias.push(i);
            }
        }

        // Calcula o hash da proxima janela usando rolling hash
        if i < n - m {
            // Remove contribuicao do caractere que sai (texto[i])
            // Adiciona contribuicao do novo caractere (texto[i + m])
            hash_janela = (hash_janela + PRIMO - (texto[i] as u64).wrapping_mul(h) % PRIMO)
                % PRIMO;
            hash_janela = (hash_janela.wrapping_mul(BASE) + texto[i + m] as u64) % PRIMO;
        }
    }

    ocorrencias
}

fn main() {
    let texto = "AABAACAABAA";
    let padrao = "AABA";

    println!("Texto:  \"{}\"", texto);
    println!("Padrao: \"{}\"", padrao);
    println!();

    let resultados = rabin_karp_busca(texto, padrao);

    if resultados.is_empty() {
        println!("Padrao nao encontrado.");
    } else {
        println!("Padrao encontrado em {} posicao(oes):", resultados.len());
        for pos in &resultados {
            println!("  Posicao {}: \"{}\"", pos, &texto[*pos..*pos + padrao.len()]);
        }
    }
}

Exemplo de Execucao

Texto:  "AABAACAABAA"
Padrao: "AABA"

Padrao encontrado em 2 posicao(oes):
  Posicao 0: "AABA"
  Posicao 6: "AABA"

Trace detalhado:

Texto:  A A B A A C A A B A A
        0 1 2 3 4 5 6 7 8 9 10

hash_padrao = hash("AABA") = H_p

i=0: janela "AABA" hash=H_p  == H_p -> verifica -> MATCH pos 0
i=1: janela "ABAA" hash=...  != H_p -> pula
i=2: janela "BAAC" hash=...  != H_p -> pula
i=3: janela "AACA" hash=...  != H_p -> pula
i=4: janela "ACAA" hash=...  != H_p -> pula
i=5: janela "CAAB" hash=...  != H_p -> pula
i=6: janela "AABA" hash=H_p  == H_p -> verifica -> MATCH pos 6
i=7: janela "ABAA" hash=...  != H_p -> pula

Variacoes e Otimizacoes

1. Busca de Multiplos Padroes

A grande forca do Rabin-Karp: buscar varios padroes de mesmo comprimento simultaneamente.

use std::collections::HashMap;

/// Busca multiplos padroes de mesmo comprimento no texto.
/// Retorna um mapa: padrao -> lista de posicoes.
fn rabin_karp_multi(texto: &str, padroes: &[&str]) -> HashMap<String, Vec<usize>> {
    let mut resultados: HashMap<String, Vec<usize>> = HashMap::new();

    if padroes.is_empty() {
        return resultados;
    }

    // Agrupa padroes por comprimento
    let mut por_comprimento: HashMap<usize, Vec<&str>> = HashMap::new();
    for &p in padroes {
        por_comprimento.entry(p.len()).or_default().push(p);
    }

    let texto_bytes = texto.as_bytes();
    let n = texto_bytes.len();

    for (&m, grupo) in &por_comprimento {
        if m == 0 || m > n {
            continue;
        }

        // Calcula hashes de todos os padroes deste grupo
        let mut hashes_padroes: HashMap<u64, Vec<&str>> = HashMap::new();
        for &p in grupo {
            let mut h: u64 = 0;
            for &b in p.as_bytes() {
                h = (h.wrapping_mul(BASE) + b as u64) % PRIMO;
            }
            hashes_padroes.entry(h).or_default().push(p);
        }

        let potencia_h = potencia_modular(BASE, (m - 1) as u64, PRIMO);
        let mut hash_janela: u64 = 0;

        // Hash da primeira janela
        for i in 0..m {
            hash_janela = (hash_janela.wrapping_mul(BASE) + texto_bytes[i] as u64) % PRIMO;
        }

        for i in 0..=(n - m) {
            // Verifica se o hash da janela corresponde a algum padrao
            if let Some(candidatos) = hashes_padroes.get(&hash_janela) {
                let janela = &texto[i..i + m];
                for &p in candidatos {
                    if janela == p {
                        resultados.entry(p.to_string()).or_default().push(i);
                    }
                }
            }

            // Rolling hash para proxima janela
            if i < n - m {
                hash_janela = (hash_janela + PRIMO
                    - (texto_bytes[i] as u64).wrapping_mul(potencia_h) % PRIMO)
                    % PRIMO;
                hash_janela =
                    (hash_janela.wrapping_mul(BASE) + texto_bytes[i + m] as u64) % PRIMO;
            }
        }
    }

    resultados
}

fn main() {
    let texto = "O rato roeu a roupa do rei de roma";
    let padroes = vec!["rato", "roeu", "roma", "reis"];

    println!("Texto: \"{}\"", texto);
    println!("Padroes: {:?}", padroes);
    println!();

    let resultados = rabin_karp_multi(texto, &padroes);
    for (padrao, posicoes) in &resultados {
        println!("\"{}\" encontrado em: {:?}", padrao, posicoes);
    }
}

2. Duplo Hashing para Reduzir Colisoes

Usar dois hashes independentes reduz drasticamente a chance de colisao:

const BASE2: u64 = 31;
const PRIMO2: u64 = 999_999_937;

/// Rabin-Karp com duplo hashing para colisoes quase zero.
fn rabin_karp_duplo_hash(texto: &str, padrao: &str) -> Vec<usize> {
    let texto = texto.as_bytes();
    let padrao = padrao.as_bytes();
    let n = texto.len();
    let m = padrao.len();

    if m == 0 || m > n {
        return Vec::new();
    }

    let h1 = potencia_modular(BASE, (m - 1) as u64, PRIMO);
    let h2 = potencia_modular(BASE2, (m - 1) as u64, PRIMO2);

    // Calcula ambos os hashes do padrao e da primeira janela
    let (mut hp1, mut hp2) = (0u64, 0u64);
    let (mut hj1, mut hj2) = (0u64, 0u64);

    for i in 0..m {
        hp1 = (hp1.wrapping_mul(BASE) + padrao[i] as u64) % PRIMO;
        hp2 = (hp2.wrapping_mul(BASE2) + padrao[i] as u64) % PRIMO2;
        hj1 = (hj1.wrapping_mul(BASE) + texto[i] as u64) % PRIMO;
        hj2 = (hj2.wrapping_mul(BASE2) + texto[i] as u64) % PRIMO2;
    }

    let mut ocorrencias = Vec::new();

    for i in 0..=(n - m) {
        // Ambos os hashes devem coincidir
        if hp1 == hj1 && hp2 == hj2 {
            // Verificacao opcional (quase nunca falsos positivos com duplo hash)
            if texto[i..i + m] == padrao[..] {
                ocorrencias.push(i);
            }
        }

        if i < n - m {
            hj1 = (hj1 + PRIMO - (texto[i] as u64).wrapping_mul(h1) % PRIMO) % PRIMO;
            hj1 = (hj1.wrapping_mul(BASE) + texto[i + m] as u64) % PRIMO;

            hj2 = (hj2 + PRIMO2 - (texto[i] as u64).wrapping_mul(h2) % PRIMO2) % PRIMO2;
            hj2 = (hj2.wrapping_mul(BASE2) + texto[i + m] as u64) % PRIMO2;
        }
    }

    ocorrencias
}

3. Deteccao de Plagio (Substrings Comuns)

/// Encontra todas as substrings comuns de comprimento k entre dois textos.
fn substrings_comuns(texto1: &str, texto2: &str, k: usize) -> Vec<String> {
    use std::collections::HashSet;

    let bytes1 = texto1.as_bytes();
    let bytes2 = texto2.as_bytes();

    if k == 0 || k > bytes1.len() || k > bytes2.len() {
        return Vec::new();
    }

    let h = potencia_modular(BASE, (k - 1) as u64, PRIMO);

    // Calcula todos os hashes do texto1
    let mut hashes1: HashMap<u64, Vec<usize>> = HashMap::new();
    let mut hash: u64 = 0;
    for i in 0..k {
        hash = (hash.wrapping_mul(BASE) + bytes1[i] as u64) % PRIMO;
    }
    hashes1.entry(hash).or_default().push(0);

    for i in 1..=(bytes1.len() - k) {
        hash = (hash + PRIMO - (bytes1[i - 1] as u64).wrapping_mul(h) % PRIMO) % PRIMO;
        hash = (hash.wrapping_mul(BASE) + bytes1[i + k - 1] as u64) % PRIMO;
        hashes1.entry(hash).or_default().push(i);
    }

    // Busca hashes coincidentes no texto2
    let mut comuns: HashSet<String> = HashSet::new();
    hash = 0;
    for i in 0..k {
        hash = (hash.wrapping_mul(BASE) + bytes2[i] as u64) % PRIMO;
    }
    if let Some(posicoes) = hashes1.get(&hash) {
        for &pos in posicoes {
            if bytes1[pos..pos + k] == bytes2[0..k] {
                comuns.insert(texto2[0..k].to_string());
            }
        }
    }

    for i in 1..=(bytes2.len() - k) {
        hash = (hash + PRIMO - (bytes2[i - 1] as u64).wrapping_mul(h) % PRIMO) % PRIMO;
        hash = (hash.wrapping_mul(BASE) + bytes2[i + k - 1] as u64) % PRIMO;
        if let Some(posicoes) = hashes1.get(&hash) {
            for &pos in posicoes {
                if bytes1[pos..pos + k] == bytes2[i..i + k] {
                    comuns.insert(texto2[i..i + k].to_string());
                }
            }
        }
    }

    comuns.into_iter().collect()
}

Aplicacoes Praticas

Deteccao de Conteudo Duplicado

/// Verifica se um trecho significativo de um texto aparece em outro.
/// Retorna a porcentagem de cobertura (quantos trechos do texto2
/// foram encontrados no texto1).
fn verificar_similaridade(texto1: &str, texto2: &str, tamanho_janela: usize) -> f64 {
    let bytes2 = texto2.as_bytes();
    let total_janelas = if bytes2.len() >= tamanho_janela {
        bytes2.len() - tamanho_janela + 1
    } else {
        return 0.0;
    };

    let resultados = substrings_comuns(texto1, texto2, tamanho_janela);
    let encontradas = resultados.len();

    (encontradas as f64 / total_janelas as f64) * 100.0
}

Comparacao com Outros Algoritmos

Algoritmo	Tempo Medio	Pior Caso	Multi-padrao	Espaco
Forca Bruta	O(n*m)	O(n*m)	Nao	O(1)
KMP	O(n+m)	O(n+m)	Nao	O(m)
Rabin-Karp	O(n+m)	*O(nm)**	Sim	O(1)
Aho-Corasick	O(n+z)	O(n+z)	Sim	O(soma)
Boyer-Moore	O(n/m)	O(n*m)	Nao	O(k)

O Rabin-Karp se destaca na busca de multiplos padroes de mesmo comprimento, onde apenas um hash deslizante e necessario e os hashes dos padroes sao comparados em um conjunto hash. Para padrao unico, o KMP oferece garantia de pior caso melhor.

Exercicios Praticos

Substring ciclica: Dadas duas strings A e B de mesmo comprimento, determine se B e uma rotacao ciclica de A. Dica: use Rabin-Karp para buscar B em A+A.
K-gramas mais frequentes: Dado um texto e um valor k, encontre o k-grama (substring de comprimento k) mais frequente. Use rolling hash para calcular todos os hashes em O(n).
Plagio em documentos: Implemente um detector de plagio que, dados dois textos, encontre todos os trechos de pelo menos 20 caracteres em comum. Calcule um indice de similaridade.
Anagramas em substring: Dado um texto T e um padrao P, encontre todas as posicoes em T onde comeca uma substring que e anagrama de P. Dica: use um hash que seja invariante a ordem dos caracteres (por exemplo, soma dos hashes individuais).

Veja Tambem

String na Biblioteca Padrao – manipulacao de strings em Rust
Vec: Vetores Dinamicos – armazenamento de resultados
HashMap – tabelas hash usadas na busca multi-padrao
Iteradores em Rust – processamento funcional de colecoes
Algoritmo KMP – busca de padrao unico com garantia linear
Hashing de Strings – tecnicas de hashing polinomial