hash(s) = s[0]*p^(n-1) + s[1]*p^(n-2) + ... + s[n-1]*p^0  (mod M)

String: "abcab"   base=31, mod=10^9+7

hash = a*31⁴ + b*31³ + c*31² + a*31 + b
     = 1*923521 + 2*29791 + 3*961 + 1*31 + 2
     = 923521 + 59582 + 2883 + 31 + 2
     = 986019

Prefix hashes (para comparar substrings em O(1)):
  h[0] = 0
  h[1] = a = 1
  h[2] = a*31 + b = 33
  h[3] = a*31² + b*31 + c = 1026
  h[4] = a*31³ + b*31² + c*31 + a = 31808
  h[5] = a*31⁴ + b*31³ + c*31² + a*31 + b = 986019

Hash de substring s[l..r]:
  hash(s[1..3]) = h[3] - h[1]*31² = 1026 - 961 = 65
                = b*31 + c = 2*31 + 3 = 65 ✓

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

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

/// Calcula o hash polinomial de uma string.
pub fn hashString(s: []const u8) u64 {
    var h: u64 = 0;
    for (s) |c| {
        h = (h * BASE + c) % MOD;
    }
    return h;
}

/// Estrutura para comparação eficiente de substrings em O(1).
pub const StringHasher = struct {
    prefixo: []u64,
    potencia: []u64,
    allocator: Allocator,

    pub fn init(allocator: Allocator, s: []const u8) !StringHasher {
        const n = s.len;
        const prefixo = try allocator.alloc(u64, n + 1);
        const potencia = try allocator.alloc(u64, n + 1);

        prefixo[0] = 0;
        potencia[0] = 1;

        for (0..n) |i| {
            prefixo[i + 1] = (prefixo[i] * BASE + s[i]) % MOD;
            potencia[i + 1] = (potencia[i] * BASE) % MOD;
        }

        return .{
            .prefixo = prefixo,
            .potencia = potencia,
            .allocator = allocator,
        };
    }

    pub fn deinit(self: *StringHasher) void {
        self.allocator.free(self.prefixo);
        self.allocator.free(self.potencia);
    }

    /// Retorna o hash da substring s[l..r] (inclusive l, exclusivo r).
    pub fn hashSubstring(self: *const StringHasher, l: usize, r: usize) u64 {
        return (self.prefixo[r] + MOD - (self.prefixo[l] * self.potencia[r - l]) % MOD) % MOD;
    }

    /// Verifica se duas substrings são iguais em O(1).
    pub fn substringsIguais(
        self: *const StringHasher,
        l1: usize,
        r1: usize,
        outro: *const StringHasher,
        l2: usize,
        r2: usize,
    ) bool {
        if (r1 - l1 != r2 - l2) return false;
        return self.hashSubstring(l1, r1) == outro.hashSubstring(l2, r2);
    }
};

/// Double hashing para reduzir colisões.
pub const DoubleHasher = struct {
    h1: StringHasher,
    h2: StringHasher,

    const MOD2: u64 = 1_000_000_009;
    const BASE2: u64 = 37;

    pub fn init(allocator: Allocator, s: []const u8) !DoubleHasher {
        const n = s.len;
        const prefixo2 = try allocator.alloc(u64, n + 1);
        const potencia2 = try allocator.alloc(u64, n + 1);
        prefixo2[0] = 0;
        potencia2[0] = 1;
        for (0..n) |i| {
            prefixo2[i + 1] = (prefixo2[i] * BASE2 + s[i]) % MOD2;
            potencia2[i + 1] = (potencia2[i] * BASE2) % MOD2;
        }

        return .{
            .h1 = try StringHasher.init(allocator, s),
            .h2 = .{
                .prefixo = prefixo2,
                .potencia = potencia2,
                .allocator = allocator,
            },
        };
    }

    pub fn deinit(self: *DoubleHasher) void {
        self.h1.deinit();
        self.h2.deinit();
    }

    pub fn hashSubstring(self: *const DoubleHasher, l: usize, r: usize) [2]u64 {
        return .{
            self.h1.hashSubstring(l, r),
            self.h2.hashSubstring(l, r),
        };
    }
};

/// Conta substrings distintas de comprimento k.
pub fn contarDistintas(allocator: Allocator, s: []const u8, k: usize) !u32 {
    if (s.len < k) return 0;

    var hasher = try StringHasher.init(allocator, s);
    defer hasher.deinit();

    var conjunto = std.AutoHashMap(u64, void).init(allocator);
    defer conjunto.deinit();

    for (0..s.len - k + 1) |i| {
        const h = hasher.hashSubstring(i, i + k);
        try conjunto.put(h, {});
    }

    return @intCast(conjunto.count());
}

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

    // Hash simples
    const palavras = [_][]const u8{ "zig", "zag", "zig", "ziglang" };
    try stdout.print("Hashes:\n", .{});
    for (palavras) |p| {
        try stdout.print("  \"{s}\" → {d}\n", .{ p, hashString(p) });
    }

    // Comparação de substrings
    const texto = "abcabcabc";
    var hasher = try StringHasher.init(allocator, texto);
    defer hasher.deinit();

    try stdout.print("\nTexto: \"{s}\"\n", .{texto});
    try stdout.print("s[0..3] == s[3..6]? {}\n", .{
        hasher.substringsIguais(&hasher, 0, 3, &hasher, 3, 6),
    });
    try stdout.print("s[0..3] == s[1..4]? {}\n", .{
        hasher.substringsIguais(&hasher, 0, 3, &hasher, 1, 4),
    });

    // Substrings distintas
    const distintas = try contarDistintas(allocator, "abcab", 2);
    try stdout.print("\nSubstrings distintas de comprimento 2 em \"abcab\": {d}\n", .{distintas});
}