Algoritmo de Manacher em Rust

/// Encontra a maior substring palindromica usando o algoritmo de Manacher.
/// Retorna a substring palindromica e sua posicao no texto original.
fn manacher(texto: &str) -> (String, usize) {
    let bytes = texto.as_bytes();
    let n = bytes.len();

    if n == 0 {
        return (String::new(), 0);
    }

    // Constroi a string transformada com separadores '#'
    // "#a#b#c#" para "abc"
    let mut t: Vec<u8> = Vec::with_capacity(2 * n + 1);
    for &b in bytes {
        t.push(b'#');
        t.push(b);
    }
    t.push(b'#');

    let t_len = t.len();
    let mut p = vec![0usize; t_len]; // raio do palindromo em cada posicao
    let mut centro = 0usize; // centro do palindromo com maior borda direita
    let mut borda_dir = 0usize; // borda direita desse palindromo

    for i in 0..t_len {
        // Usa o espelho se estamos dentro da borda direita
        if i < borda_dir {
            let espelho = 2 * centro - i;
            p[i] = p[espelho].min(borda_dir - i);
        }

        // Tenta expandir alem do valor inicial
        let mut esq = i as isize - p[i] as isize - 1;
        let mut dir = i + p[i] + 1;

        while esq >= 0 && dir < t_len && t[esq as usize] == t[dir] {
            p[i] += 1;
            esq -= 1;
            dir += 1;
        }

        // Atualiza centro e borda se expandimos alem
        if i + p[i] > borda_dir {
            centro = i;
            borda_dir = i + p[i];
        }
    }

    // Encontra o maior palindromo
    let mut max_raio = 0;
    let mut max_centro = 0;

    for i in 0..t_len {
        if p[i] > max_raio {
            max_raio = p[i];
            max_centro = i;
        }
    }

    // Converte de volta para coordenadas do texto original
    let inicio = (max_centro - max_raio) / 2;
    let comprimento = max_raio;

    (texto[inicio..inicio + comprimento].to_string(), inicio)
}

/// Encontra TODOS os palindromos centrados em cada posicao.
/// Retorna um vetor de (inicio, comprimento) para cada palindromo maximal.
fn todos_palindromos(texto: &str) -> Vec<(usize, usize)> {
    let bytes = texto.as_bytes();
    let n = bytes.len();

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

    let mut t: Vec<u8> = Vec::with_capacity(2 * n + 1);
    for &b in bytes {
        t.push(b'#');
        t.push(b);
    }
    t.push(b'#');

    let t_len = t.len();
    let mut p = vec![0usize; t_len];
    let mut centro = 0usize;
    let mut borda_dir = 0usize;

    for i in 0..t_len {
        if i < borda_dir {
            let espelho = 2 * centro - i;
            p[i] = p[espelho].min(borda_dir - i);
        }

        let mut esq = i as isize - p[i] as isize - 1;
        let mut dir = i + p[i] + 1;

        while esq >= 0 && dir < t_len && t[esq as usize] == t[dir] {
            p[i] += 1;
            esq -= 1;
            dir += 1;
        }

        if i + p[i] > borda_dir {
            centro = i;
            borda_dir = i + p[i];
        }
    }

    // Coleta palindromos com comprimento >= 2
    let mut palindromos = Vec::new();

    for i in 0..t_len {
        if p[i] >= 2 {
            let inicio = (i - p[i]) / 2;
            let comprimento = p[i];
            palindromos.push((inicio, comprimento));
        }
    }

    palindromos
}

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

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

    // Maior palindromo
    let (palindromo, posicao) = manacher(texto);
    println!(
        "Maior palindromo: \"{}\" (posicao {}, comprimento {})",
        palindromo,
        posicao,
        palindromo.len()
    );
    println!();

    // Todos os palindromos
    let todos = todos_palindromos(texto);
    println!("Todos os palindromos (comprimento >= 2):");
    for (inicio, comprimento) in &todos {
        println!(
            "  posicao {}: \"{}\"",
            inicio,
            &texto[*inicio..*inicio + *comprimento]
        );
    }
    println!();

    // Mais exemplos
    let exemplos = vec![
        "racecar",
        "babad",
        "cbbd",
        "forgeeksskeegfor",
    ];

    println!("Mais exemplos:");
    for ex in &exemplos {
        let (pal, pos) = manacher(ex);
        println!("  \"{}\" -> \"{}\" (pos {})", ex, pal, pos);
    }
}

/// Encontra o maior palindromo expandindo ao redor de cada centro.
/// Complexidade: O(n^2) no pior caso, mas simples de implementar.
fn maior_palindromo_expansao(texto: &str) -> (String, usize) {
    let bytes = texto.as_bytes();
    let n = bytes.len();

    if n == 0 {
        return (String::new(), 0);
    }

    let mut melhor_inicio = 0;
    let mut melhor_comprimento = 1;

    // Funcao auxiliar para expandir ao redor de um centro
    let expandir = |mut esq: isize, mut dir: usize| -> (usize, usize) {
        while esq >= 0 && dir < n && bytes[esq as usize] == bytes[dir] {
            esq -= 1;
            dir += 1;
        }
        let inicio = (esq + 1) as usize;
        let comprimento = dir - inicio;
        (inicio, comprimento)
    };

    for i in 0..n {
        // Palindromo impar (centro em i)
        let (inicio, comp) = expandir(i as isize, i);
        if comp > melhor_comprimento {
            melhor_inicio = inicio;
            melhor_comprimento = comp;
        }

        // Palindromo par (centro entre i e i+1)
        if i + 1 < n {
            let (inicio, comp) = expandir(i as isize, i + 1);
            if comp > melhor_comprimento {
                melhor_inicio = inicio;
                melhor_comprimento = comp;
            }
        }
    }

    (
        texto[melhor_inicio..melhor_inicio + melhor_comprimento].to_string(),
        melhor_inicio,
    )
}

/// Conta o numero total de substrings palindromicas (incluindo repeticoes).
fn contar_palindromos(texto: &str) -> usize {
    let bytes = texto.as_bytes();
    let n = bytes.len();

    if n == 0 {
        return 0;
    }

    // Constroi string transformada
    let mut t: Vec<u8> = Vec::with_capacity(2 * n + 1);
    for &b in bytes {
        t.push(b'#');
        t.push(b);
    }
    t.push(b'#');

    let t_len = t.len();
    let mut p = vec![0usize; t_len];
    let mut centro = 0;
    let mut borda_dir = 0;

    for i in 0..t_len {
        if i < borda_dir {
            let espelho = 2 * centro - i;
            p[i] = p[espelho].min(borda_dir - i);
        }

        let mut esq = i as isize - p[i] as isize - 1;
        let mut dir = i + p[i] + 1;

        while esq >= 0 && dir < t_len && t[esq as usize] == t[dir] {
            p[i] += 1;
            esq -= 1;
            dir += 1;
        }

        if i + p[i] > borda_dir {
            centro = i;
            borda_dir = i + p[i];
        }
    }

    // Cada P[i] no indice impar (caractere original) contribui com
    // (P[i] + 1) / 2 palindromos impares.
    // Cada P[i] no indice par (#) contribui com P[i] / 2 palindromos pares.
    let mut total = 0usize;
    for i in 0..t_len {
        if i % 2 == 1 {
            // Indice impar = caractere original
            total += (p[i] + 1) / 2; // inclui o proprio caractere (palindromo de tamanho 1)
        } else {
            // Indice par = separador '#'
            total += p[i] / 2;
        }
    }

    // Subtrai os palindromos de comprimento 1 se nao quiser conta-los
    // total -= n;  // descomente para excluir palindromos de tamanho 1

    total
}

fn main() {
    let texto = "abaab";
    let total = contar_palindromos(texto);
    println!(
        "Numero de substrings palindromicas em \"{}\": {}",
        texto, total
    );
    // Palindromos: a, b, a, a, b, aba, aa, abaab? Nao.
    // a(0), b(1), a(2), a(3), b(4), aba(0-2), aa(2-3), baab? Nao.
    // Total: 7 (incluindo caracteres individuais)
}

/// Para cada posicao i, retorna o comprimento do maior palindromo
/// que TERMINA na posicao i. Util para problemas de DP com palindromos.
fn palindromos_terminando_em(texto: &str) -> Vec<usize> {
    let n = texto.len();
    let (_, _) = manacher(texto);

    let bytes = texto.as_bytes();
    let mut resultado = vec![1usize; n]; // no minimo o caractere sozinho

    for i in 0..n {
        // Expande palindromo impar terminando em i
        for raio in 1..=i {
            if i + 1 > raio * 2 {
                let inicio = i - 2 * raio;
                if bytes[inicio] == bytes[i] {
                    let meio_ok = resultado[i - 1] >= 2 * raio - 1
                        || (inicio + 1 <= i - 1
                            && texto[inicio + 1..i] == texto[inicio + 1..i]);
                    // Simplificacao: verifica diretamente
                    let sub = &bytes[inicio..=i];
                    let eh_palindromo = sub.iter().zip(sub.iter().rev()).all(|(a, b)| a == b);
                    if eh_palindromo {
                        resultado[i] = resultado[i].max(2 * raio + 1);
                    }
                }
            }
            // Para eficiencia, podemos limitar as verificacoes
            if raio > 10 {
                break;
            }
        }
    }

    resultado
}

/// Encontra todas as palavras palindromicas em um texto.
fn encontrar_palindromos_palavras(texto: &str) -> Vec<String> {
    let mut palindromos = Vec::new();

    for palavra in texto.split_whitespace() {
        // Remove pontuacao
        let limpa: String = palavra
            .chars()
            .filter(|c| c.is_alphanumeric())
            .collect();
        let limpa_lower = limpa.to_lowercase();

        if limpa_lower.len() >= 2 {
            let bytes = limpa_lower.as_bytes();
            let eh_palindromo = bytes.iter().zip(bytes.iter().rev()).all(|(a, b)| a == b);
            if eh_palindromo {
                palindromos.push(limpa);
            }
        }
    }

    palindromos
}

/// Particiona uma string no menor numero de substrings palindromicas.
fn particao_palindromica(texto: &str) -> Vec<String> {
    let bytes = texto.as_bytes();
    let n = bytes.len();

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

    // DP: dp[i] = numero minimo de cortes para texto[0..i]
    let mut dp = vec![usize::MAX; n + 1];
    let mut corte = vec![0usize; n + 1]; // onde foi feito o melhor corte
    dp[0] = 0;

    // Pre-computa: eh_palindromo[i][j] para substrings curtas
    let eh_pal = |i: usize, j: usize| -> bool {
        let sub = &bytes[i..=j];
        sub.iter().zip(sub.iter().rev()).all(|(a, b)| a == b)
    };

    for i in 1..=n {
        for j in 0..i {
            if dp[j] != usize::MAX && eh_pal(j, i - 1) {
                if dp[j] + 1 < dp[i] {
                    dp[i] = dp[j] + 1;
                    corte[i] = j;
                }
            }
        }
    }

    // Reconstroi a particao
    let mut resultado = Vec::new();
    let mut pos = n;
    while pos > 0 {
        resultado.push(texto[corte[pos]..pos].to_string());
        pos = corte[pos];
    }
    resultado.reverse();
    resultado
}

fn main() {
    let texto = "abacdca";
    let particao = particao_palindromica(texto);
    println!("Particao palindromica de \"{}\": {:?}", texto, particao);

    let texto2 = "O ovo da aba arara e legal";
    let pals = encontrar_palindromos_palavras(texto2);
    println!("Palavras palindromicas: {:?}", pals);
}