Hashing de Strings em Rust

/// Constantes para hash polinomial.
/// Base prima e modulo primo grande para minimizar colisoes.
const BASE: u64 = 31;
const MOD: u64 = 1_000_000_007;

/// Estrutura para hashing de strings com pre-processamento de prefixos.
/// Permite consultas de hash de substrings em O(1).
struct StringHasher {
    prefix_hash: Vec<u64>,  // hash de cada prefixo
    potencias: Vec<u64>,     // base^i mod MOD pre-calculadas
    n: usize,
}

impl StringHasher {
    /// Constroi o hasher a partir de uma string em O(n).
    fn novo(texto: &str) -> Self {
        let bytes = texto.as_bytes();
        let n = bytes.len();

        let mut prefix_hash = vec![0u64; n + 1];
        let mut potencias = vec![1u64; n + 1];

        // Pre-calcula potencias de base
        for i in 1..=n {
            potencias[i] = potencias[i - 1].wrapping_mul(BASE) % MOD;
        }

        // Pre-calcula hashes de prefixos
        for i in 0..n {
            // Valor do caractere: usamos (byte - b'a' + 1) para evitar hash 0
            // para strings de 'a'. Se a string pode conter qualquer byte, use byte + 1.
            let valor = (bytes[i] as u64).wrapping_add(1);
            prefix_hash[i + 1] = (prefix_hash[i].wrapping_mul(BASE) + valor) % MOD;
        }

        StringHasher {
            prefix_hash,
            potencias,
            n,
        }
    }

    /// Retorna o hash da substring s[esquerda..direita] em O(1).
    /// Indices baseados em 0, intervalo semi-aberto [esquerda, direita).
    fn hash_substring(&self, esquerda: usize, direita: usize) -> u64 {
        assert!(esquerda <= direita && direita <= self.n);

        let hash = (self.prefix_hash[direita]
            + MOD
            - self.prefix_hash[esquerda]
                .wrapping_mul(self.potencias[direita - esquerda])
                % MOD)
            % MOD;

        hash
    }

    /// Compara duas substrings em O(1).
    /// Retorna true se s[l1..r1] == s[l2..r2].
    fn substrings_iguais(&self, l1: usize, r1: usize, l2: usize, r2: usize) -> bool {
        if r1 - l1 != r2 - l2 {
            return false;
        }
        self.hash_substring(l1, r1) == self.hash_substring(l2, r2)
    }
}

/// Hasher com duplo hash para colisoes quase zero.
struct DuploHasher {
    hasher1: StringHasher,
    prefix_hash2: Vec<u64>,
    potencias2: Vec<u64>,
    n: usize,
}

const BASE2: u64 = 37;
const MOD2: u64 = 999_999_937;

impl DuploHasher {
    fn novo(texto: &str) -> Self {
        let bytes = texto.as_bytes();
        let n = bytes.len();

        let hasher1 = StringHasher::novo(texto);

        let mut prefix_hash2 = vec![0u64; n + 1];
        let mut potencias2 = vec![1u64; n + 1];

        for i in 1..=n {
            potencias2[i] = potencias2[i - 1].wrapping_mul(BASE2) % MOD2;
        }

        for i in 0..n {
            let valor = (bytes[i] as u64).wrapping_add(1);
            prefix_hash2[i + 1] = (prefix_hash2[i].wrapping_mul(BASE2) + valor) % MOD2;
        }

        DuploHasher {
            hasher1,
            prefix_hash2,
            potencias2,
            n,
        }
    }

    /// Retorna um par (hash1, hash2) para a substring.
    fn hash_substring(&self, esquerda: usize, direita: usize) -> (u64, u64) {
        let h1 = self.hasher1.hash_substring(esquerda, direita);
        let h2 = (self.prefix_hash2[direita]
            + MOD2
            - self.prefix_hash2[esquerda]
                .wrapping_mul(self.potencias2[direita - esquerda])
                % MOD2)
            % MOD2;

        (h1, h2)
    }

    fn substrings_iguais(&self, l1: usize, r1: usize, l2: usize, r2: usize) -> bool {
        if r1 - l1 != r2 - l2 {
            return false;
        }
        self.hash_substring(l1, r1) == self.hash_substring(l2, r2)
    }
}

fn main() {
    let texto = "abcabcxyzabc";

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

    let hasher = StringHasher::novo(texto);

    // Compara substrings
    let pares = vec![
        ((0, 3), (3, 6)),   // "abc" vs "abc"
        ((0, 3), (9, 12)),  // "abc" vs "abc"
        ((0, 3), (6, 9)),   // "abc" vs "xyz"
        ((0, 6), (3, 9)),   // "abcabc" vs "abcxyz"
    ];

    println!("Comparacao de substrings (hash simples):");
    for ((l1, r1), (l2, r2)) in &pares {
        let h1 = hasher.hash_substring(*l1, *r1);
        let h2 = hasher.hash_substring(*l2, *r2);
        let iguais = hasher.substrings_iguais(*l1, *r1, *l2, *r2);

        println!(
            "  \"{}\" (hash={}) vs \"{}\" (hash={}) -> {}",
            &texto[*l1..*r1],
            h1,
            &texto[*l2..*r2],
            h2,
            if iguais { "IGUAIS" } else { "DIFERENTES" }
        );
    }

    // Duplo hash
    println!();
    let duplo = DuploHasher::novo(texto);
    println!("Duplo hash para \"abc\"[0..3]: {:?}", duplo.hash_substring(0, 3));
    println!("Duplo hash para \"abc\"[3..6]: {:?}", duplo.hash_substring(3, 6));
    println!("Duplo hash para \"xyz\"[6..9]: {:?}", duplo.hash_substring(6, 9));
}

use std::collections::HashMap;

/// Hash invariante a ordem para deteccao de anagramas.
/// Usa a soma dos hashes individuais de cada caractere.
fn hash_anagrama(s: &str) -> u64 {
    // Usamos primos distintos para cada caractere para evitar colisoes
    let primos: Vec<u64> = vec![
        2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
        31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
        73, 79, 83, 89, 97, 101,
    ];

    let mut hash: u64 = 1;
    for byte in s.bytes() {
        let idx = (byte.to_ascii_lowercase() - b'a') as usize;
        if idx < primos.len() {
            hash = hash.wrapping_mul(primos[idx]) % MOD;
        }
    }
    hash
}

/// Encontra todos os pares de anagramas em uma lista de strings.
fn encontrar_anagramas(palavras: &[&str]) -> Vec<(String, String)> {
    let mut mapa: HashMap<u64, Vec<&str>> = HashMap::new();

    for &palavra in palavras {
        let hash = hash_anagrama(palavra);
        mapa.entry(hash).or_default().push(palavra);
    }

    let mut pares = Vec::new();
    for grupo in mapa.values() {
        if grupo.len() >= 2 {
            for i in 0..grupo.len() {
                for j in (i + 1)..grupo.len() {
                    // Verifica se realmente sao anagramas (confirma contra colisao)
                    let mut chars1: Vec<char> = grupo[i].chars().collect();
                    let mut chars2: Vec<char> = grupo[j].chars().collect();
                    chars1.sort();
                    chars2.sort();
                    if chars1 == chars2 {
                        pares.push((grupo[i].to_string(), grupo[j].to_string()));
                    }
                }
            }
        }
    }
    pares
}

/// Encontra todas as posicoes onde substrings do texto sao anagramas do padrao.
fn buscar_anagramas_substring(texto: &str, padrao: &str) -> Vec<usize> {
    let texto_bytes = texto.as_bytes();
    let padrao_bytes = padrao.as_bytes();
    let n = texto_bytes.len();
    let m = padrao_bytes.len();

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

    // Conta a frequencia de cada caractere no padrao
    let mut freq_padrao = [0i32; 256];
    for &b in padrao_bytes {
        freq_padrao[b as usize] += 1;
    }

    // Janela deslizante
    let mut freq_janela = [0i32; 256];
    let mut posicoes = Vec::new();

    // Inicializa a primeira janela
    for i in 0..m {
        freq_janela[texto_bytes[i] as usize] += 1;
    }

    if freq_janela == freq_padrao {
        posicoes.push(0);
    }

    // Desliza a janela
    for i in 1..=(n - m) {
        // Remove caractere que sai
        freq_janela[texto_bytes[i - 1] as usize] -= 1;
        // Adiciona caractere que entra
        freq_janela[texto_bytes[i + m - 1] as usize] += 1;

        if freq_janela == freq_padrao {
            posicoes.push(i);
        }
    }

    posicoes
}

fn main() {
    // Encontrar anagramas
    let palavras = vec!["roma", "amor", "mora", "ramo", "gato", "toga"];
    let pares = encontrar_anagramas(&palavras);
    println!("Pares de anagramas:");
    for (a, b) in &pares {
        println!("  \"{}\" <-> \"{}\"", a, b);
    }
    println!();

    // Busca de anagramas como substrings
    let texto = "cbaebabacd";
    let padrao = "abc";
    let posicoes = buscar_anagramas_substring(texto, padrao);
    println!(
        "Anagramas de \"{}\" em \"{}\": posicoes {:?}",
        padrao, texto, posicoes
    );
    for pos in &posicoes {
        println!("  posicao {}: \"{}\"", pos, &texto[*pos..*pos + padrao.len()]);
    }
}

use std::collections::HashSet;

/// Remove strings duplicadas usando hashing.
/// Mais eficiente que ordenar + dedup para strings longas.
fn deduplicar(strings: &[&str]) -> Vec<String> {
    let mut vistos: HashSet<u64> = HashSet::new();
    let mut resultado = Vec::new();

    for &s in strings {
        let hasher = StringHasher::novo(s);
        let hash = hasher.hash_substring(0, s.len());

        if vistos.insert(hash) {
            resultado.push(s.to_string());
        }
    }

    resultado
}

/// Encontra substrings duplicadas de comprimento k em um texto.
fn substrings_duplicadas(texto: &str, k: usize) -> Vec<String> {
    let n = texto.len();
    if k == 0 || k > n {
        return Vec::new();
    }

    let hasher = StringHasher::novo(texto);
    let mut vistos: HashMap<u64, usize> = HashMap::new(); // hash -> primeira posicao
    let mut duplicadas: HashSet<String> = HashSet::new();

    for i in 0..=(n - k) {
        let hash = hasher.hash_substring(i, i + k);

        if let Some(&pos_anterior) = vistos.get(&hash) {
            // Confirma que realmente sao iguais (contra colisoes)
            if texto[i..i + k] == texto[pos_anterior..pos_anterior + k] {
                duplicadas.insert(texto[i..i + k].to_string());
            }
        } else {
            vistos.insert(hash, i);
        }
    }

    duplicadas.into_iter().collect()
}

/// Estrutura que permite verificar palindromos em O(1) por consulta.
struct PalindromeHasher {
    frente: StringHasher,
    prefix_hash_rev: Vec<u64>,
    potencias_rev: Vec<u64>,
    n: usize,
}

impl PalindromeHasher {
    fn novo(texto: &str) -> Self {
        let n = texto.len();
        let bytes = texto.as_bytes();

        let frente = StringHasher::novo(texto);

        // Calcula hashes da string reversa
        let mut prefix_hash_rev = vec![0u64; n + 1];
        let mut potencias_rev = vec![1u64; n + 1];

        for i in 1..=n {
            potencias_rev[i] = potencias_rev[i - 1].wrapping_mul(BASE) % MOD;
        }

        for i in 0..n {
            let valor = (bytes[n - 1 - i] as u64).wrapping_add(1);
            prefix_hash_rev[i + 1] = (prefix_hash_rev[i].wrapping_mul(BASE) + valor) % MOD;
        }

        PalindromeHasher {
            frente,
            prefix_hash_rev,
            potencias_rev,
            n,
        }
    }

    /// Hash da substring reversa correspondente a s[esquerda..direita].
    fn hash_reverso(&self, esquerda: usize, direita: usize) -> u64 {
        let rev_esq = self.n - direita;
        let rev_dir = self.n - esquerda;

        (self.prefix_hash_rev[rev_dir]
            + MOD
            - self.prefix_hash_rev[rev_esq]
                .wrapping_mul(self.potencias_rev[rev_dir - rev_esq])
                % MOD)
            % MOD
    }

    /// Verifica se s[esquerda..direita] e um palindromo em O(1).
    fn eh_palindromo(&self, esquerda: usize, direita: usize) -> bool {
        self.frente.hash_substring(esquerda, direita)
            == self.hash_reverso(esquerda, direita)
    }
}

fn main() {
    let texto = "abaacaaba";
    let hasher = PalindromeHasher::novo(texto);

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

    // Testa varias substrings
    let testes = vec![
        (0, 3, "aba"),
        (0, 5, "abaac"),
        (3, 6, "aca"),
        (5, 9, "aaba"),
        (0, 9, "abaacaaba"),
    ];

    println!("Verificacao de palindromos em O(1):");
    for (l, r, desc) in &testes {
        let resultado = hasher.eh_palindromo(*l, *r);
        println!(
            "  s[{}..{}] = \"{}\" -> {}",
            l,
            r,
            desc,
            if resultado { "PALINDROMO" } else { "NAO" }
        );
    }
}

/// Busca simples de padrao usando rolling hash.
fn buscar_padrao(texto: &str, padrao: &str) -> Vec<usize> {
    let n = texto.len();
    let m = padrao.len();

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

    let hasher_texto = StringHasher::novo(texto);
    let hasher_padrao = StringHasher::novo(padrao);
    let hash_padrao = hasher_padrao.hash_substring(0, m);

    let mut posicoes = Vec::new();

    for i in 0..=(n - m) {
        if hasher_texto.hash_substring(i, i + m) == hash_padrao {
            // Confirma contra colisoes
            if texto[i..i + m] == *padrao {
                posicoes.push(i);
            }
        }
    }

    posicoes
}

/// Encontra o comprimento do maior prefixo comum entre
/// s[a..] e s[b..] em O(log n) usando hashing + busca binaria.
fn maior_prefixo_comum(hasher: &StringHasher, a: usize, b: usize, n: usize) -> usize {
    let max_len = n.saturating_sub(a).min(n.saturating_sub(b));

    let mut low = 0;
    let mut high = max_len;

    while low < high {
        let mid = low + (high - low + 1) / 2;
        if hasher.hash_substring(a, a + mid) == hasher.hash_substring(b, b + mid) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }

    low
}

fn main() {
    let texto = "abcabcxabc";
    let hasher = StringHasher::novo(texto);
    let n = texto.len();

    let a = 0; // "abcabcxabc"
    let b = 3; // "abcxabc"

    let lcp = maior_prefixo_comum(&hasher, a, b, n);
    println!(
        "Maior prefixo comum entre s[{}..] e s[{}..]: {} (\"{}\")",
        a,
        b,
        lcp,
        &texto[a..a + lcp]
    );
}

/// Analisa a taxa de colisoes para um dado conjunto de strings.
fn analisar_colisoes(strings: &[&str]) {
    let mut hashes_simples: HashMap<u64, Vec<&str>> = HashMap::new();
    let mut hashes_duplo: HashMap<(u64, u64), Vec<&str>> = HashMap::new();

    for &s in strings {
        let hasher = StringHasher::novo(s);
        let h1 = hasher.hash_substring(0, s.len());

        let duplo = DuploHasher::novo(s);
        let h2 = duplo.hash_substring(0, s.len());

        hashes_simples.entry(h1).or_default().push(s);
        hashes_duplo.entry(h2).or_default().push(s);
    }

    let colisoes_simples = hashes_simples.values().filter(|v| v.len() > 1).count();
    let colisoes_duplo = hashes_duplo.values().filter(|v| v.len() > 1).count();

    println!("Total de strings: {}", strings.len());
    println!("Hashes unicos (simples): {}", hashes_simples.len());
    println!("Colisoes (simples): {}", colisoes_simples);
    println!("Hashes unicos (duplo):   {}", hashes_duplo.len());
    println!("Colisoes (duplo):   {}", colisoes_duplo);

    // Mostra colisoes se existirem
    for (hash, grupo) in &hashes_simples {
        if grupo.len() > 1 {
            println!("  Colisao hash={}: {:?}", hash, grupo);
        }
    }
}