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

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!

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,
        });
    }
}