---
title: "Rabin-Karp em Zig — Implementação e Explicação"
url: "https://ziglang.com.br/algoritmos/rabin-karp-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/"
markdown_url: "https://ziglang.com.br/algoritmos/rabin-karp-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD"
description: "Aprenda o algoritmo Rabin-Karp de busca em strings implementado em Zig. Rolling hash para pattern matching com código funcional."
date: "2026-02-21"
author: "Zig Brasil"
---

# Rabin-Karp em Zig — Implementação e Explicação

Aprenda o algoritmo Rabin-Karp de busca em strings implementado em Zig. Rolling hash para pattern matching com código funcional.


# Rabin-Karp em Zig — Implementação e Explicação

O algoritmo **Rabin-Karp** usa **hashing** para buscar padrões em textos. Ele calcula o hash do padrão e o compara com hashes de substrings do texto usando um **rolling hash** que permite atualização incremental em O(1).

## Como Funciona

1. Calcula o hash do padrão
2. Calcula o hash da primeira janela do texto (mesma largura do padrão)
3. Desliza a janela, atualizando o hash incrementalmente
4. Quando os hashes coincidem, verifica caractere a caractere (para evitar falsos positivos)

### Rolling Hash

```
hash("abc") = a*d² + b*d + c    (d = base, mod p)
hash("bcd") = (hash("abc") - a*d²) * d + d
```

### Visualização

```
Texto:  "ABCABCDABCD"   Padrão: "ABCD"   base=256, mod=101

Hash do padrão "ABCD" = (65*256³ + 66*256² + 67*256 + 68) mod 101 = ?

Janela 1: "ABCA" → hash ≠ hash_padrão
Janela 2: "BCAB" → hash ≠ hash_padrão  (rolling: remove A, adiciona B)
Janela 3: "CABC" → hash ≠ hash_padrão
Janela 4: "ABCD" → hash == hash_padrão → verifica → MATCH na posição 3!
Janela 5: "BCDA" → hash ≠ hash_padrão
...
Janela 8: "ABCD" → hash == hash_padrão → verifica → MATCH na posição 7!
```

## Implementação em Zig

```zig
const std = @import("std");
const Allocator = std.mem.Allocator;

const BASE: u64 = 256;
const MOD: u64 = 1_000_000_007;

/// Busca todas as ocorrências do padrão no texto usando Rabin-Karp.
pub fn rabinKarp(
    allocator: Allocator,
    texto: []const u8,
    padrao: []const u8,
) ![]usize {
    var ocorrencias = std.ArrayList(usize).init(allocator);

    const n = texto.len;
    const m = padrao.len;
    if (m == 0 or n < m) return try ocorrencias.toOwnedSlice();

    // Calcula BASE^(m-1) mod MOD
    var h: u64 = 1;
    for (0..m - 1) |_| {
        h = (h * BASE) % MOD;
    }

    // Calcula hash do padrão e da primeira janela
    var hash_padrao: u64 = 0;
    var hash_texto: u64 = 0;
    for (0..m) |i| {
        hash_padrao = (hash_padrao * BASE + padrao[i]) % MOD;
        hash_texto = (hash_texto * BASE + texto[i]) % MOD;
    }

    // Desliza a janela pelo texto
    for (0..n - m + 1) |i| {
        if (hash_padrao == hash_texto) {
            // Verifica caractere a caractere (evita falsos positivos)
            if (std.mem.eql(u8, texto[i .. i + m], padrao)) {
                try ocorrencias.append(i);
            }
        }

        // Atualiza rolling hash para próxima janela
        if (i < n - m) {
            hash_texto = ((hash_texto + MOD - (texto[i] * h) % MOD) * BASE + texto[i + m]) % MOD;
        }
    }

    return try ocorrencias.toOwnedSlice();
}

/// Busca múltiplos padrões simultaneamente (vantagem do Rabin-Karp).
pub fn rabinKarpMultiplo(
    allocator: Allocator,
    texto: []const u8,
    padroes: []const []const u8,
) ![]struct { padrao_idx: usize, posicao: usize } {
    const ResultMatch = struct { padrao_idx: usize, posicao: usize };
    var resultados = std.ArrayList(ResultMatch).init(allocator);

    for (padroes, 0..) |padrao, idx| {
        const matches = try rabinKarp(allocator, texto, padrao);
        defer allocator.free(matches);
        for (matches) |pos| {
            try resultados.append(.{ .padrao_idx = idx, .posicao = pos });
        }
    }

    return try resultados.toOwnedSlice();
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // Exemplo simples
    const texto = "ABCABCDABCDAB";
    const padrao = "ABCD";

    try stdout.print("Texto:  \"{s}\"\n", .{texto});
    try stdout.print("Padrão: \"{s}\"\n\n", .{padrao});

    const matches = try rabinKarp(allocator, texto, padrao);
    defer allocator.free(matches);

    try stdout.print("Ocorrências: {d}\n", .{matches.len});
    for (matches) |pos| {
        try stdout.print("  Posição {d}\n", .{pos});
    }

    // Busca múltipla
    try stdout.print("\n--- Busca múltipla ---\n", .{});
    const padroes = [_][]const u8{ "ABC", "CD", "DAB" };
    const multi = try rabinKarpMultiplo(allocator, texto, &padroes);
    defer allocator.free(multi);

    for (multi) |r| {
        try stdout.print("  Padrão \"{s}\" na posição {d}\n", .{
            padroes[r.padrao_idx], r.posicao,
        });
    }
}
```

## Análise de Complexidade

| Caso | Tempo | Espaço |
|------|-------|--------|
| **Melhor/Médio** | O(n + m) | O(1) |
| **Pior caso** | O(n * m) — muitas colisões de hash | O(1) |

## Rabin-Karp vs KMP

| Aspecto | Rabin-Karp | KMP |
|---------|------------|-----|
| Caso médio | O(n + m) | O(n + m) |
| Pior caso | O(n * m) | O(n + m) |
| Múltiplos padrões | Eficiente | Precisa de repetição |
| Implementação | Mais simples | Mais complexa |

## Quando Usar

- **Múltiplos padrões**: a principal vantagem sobre KMP
- **Detecção de plágio**: comparar hashes de substrings de documentos
- **Busca em grandes textos**: quando colisões são raras na prática

## Recursos Relacionados

- [KMP Pattern Matching](/algoritmos/kmp-pattern-matching/) — Busca garantida O(n+m)
- [String Hashing](/algoritmos/string-hashing/) — Técnicas de hashing de strings
- [Hash Table](/estruturas-dados/hash-table/) — Estrutura baseada em hash
- [Busca Linear](/algoritmos/busca-linear/) — Busca sequencial simples