--- title: "Algoritmo Rabin-Karp em Rust" url: "https://rustlang.com.br/algoritmos/rabin-karp/" markdown_url: "https://rustlang.com.br/algoritmos/rabin-karp.MD" description: "Implementacao do algoritmo Rabin-Karp em Rust com rolling hash para busca eficiente de padroes em strings e busca de multiplos padroes." date: "2026-02-24" author: "Equipe Rust Brasil" --- # Algoritmo Rabin-Karp em Rust Implementacao do algoritmo Rabin-Karp em Rust com rolling hash para busca eficiente de padroes em strings e busca de multiplos padroes. 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(n*m) 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(n*k + soma_m), pois calculamos `k` hashes de padrao e comparamos a cada posicao. ## Implementacao em Rust ```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 { 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. ```rust 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> { let mut resultados: HashMap> = HashMap::new(); if padroes.is_empty() { return resultados; } // Agrupa padroes por comprimento let mut por_comprimento: HashMap> = 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> = 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: ```rust 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 { 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) ```rust /// Encontra todas as substrings comuns de comprimento k entre dois textos. fn substrings_comuns(texto1: &str, texto2: &str, k: usize) -> Vec { 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> = 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 = 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 ```rust /// 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(n*m)** | **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 1. **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. 2. **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). 3. **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. 4. **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](/stdlib/string/) -- manipulacao de strings em Rust - [Vec: Vetores Dinamicos](/stdlib/vec/) -- armazenamento de resultados - [HashMap](/stdlib/hashmap/) -- tabelas hash usadas na busca multi-padrao - [Iteradores em Rust](/stdlib/iterator/) -- processamento funcional de colecoes - [Algoritmo KMP](/algoritmos/kmp/) -- busca de padrao unico com garantia linear - [Hashing de Strings](/algoritmos/string-hashing/) -- tecnicas de hashing polinomial