---
title: "Algoritmo de Manacher em Rust"
url: "https://rustlang.com.br/algoritmos/manacher/"
markdown_url: "https://rustlang.com.br/algoritmos/manacher.MD"
description: "Algoritmo de Manacher em Rust para encontrar a maior substring palindromica em tempo linear O(n) com diagramas visuais e comparacoes."
date: "2026-02-24"
author: "Equipe Rust Brasil"
---

# Algoritmo de Manacher em Rust

Algoritmo de Manacher em Rust para encontrar a maior substring palindromica em tempo linear O(n) com diagramas visuais e comparacoes.


O algoritmo de Manacher resolve o problema de encontrar a **maior substring palindromica** em tempo linear O(n). Um palindromo e uma string que se le da mesma forma da esquerda para a direita e da direita para a esquerda (como "arara" ou "reviver"). Enquanto a abordagem de expandir ao redor de cada centro custa O(n^2) no pior caso, Manacher aproveita informacoes de palindromos ja descobertos para evitar comparacoes redundantes.

O algoritmo e notavel por sua elegancia: usa um **truque de transformacao** para tratar palindromos de comprimento par e impar de forma uniforme, e mantem uma "fronteira direita" que avanca monotonicamente pelo texto. Foi publicado por Glenn Manacher em 1975 e permanece como a solucao otima para este problema classico.

## Como Funciona

### O Truque da Transformacao

Para tratar uniformemente palindromos pares e impares, inserimos um caractere separador (ex.: '#') entre cada caractere e nas extremidades:

```
Original:    "abba"
Transformada: "#a#b#b#a#"

Palindromo impar "aba":    -> "#a#b#a#"    (centro no 'b')
Palindromo par   "abba":   -> "#a#b#b#a#"  (centro no '#' entre os b's)

Agora TODOS os palindromos na string transformada sao impares!
```

### Array P (Raio do Palindromo)

Para cada posicao `i` na string transformada, `P[i]` armazena o raio do maior palindromo centrado em `i`:

```
Transformada: # a # b # b # a #
Indice:       0 1 2 3 4 5 6 7 8
P:            0 1 0 1 4 1 0 1 0

Verificacao de P[4]=4:
  Centro: indice 4 (caractere '#')
  Palindromo: T[0..8] = "#a#b#b#a#"
  Raio 4: 4 caracteres para cada lado
  Corresponde ao palindromo original "abba" (comprimento = P[4] = 4)
```

### O Algoritmo: Espelho e Fronteira

A sacada do Manacher: ao calcular `P[i]`, usamos palindromos ja descobertos:

```
String: # a # b # a # b # a #
        0 1 2 3 4 5 6 7 8 9 10

Suponha que ja calculamos ate i=7 e encontramos:
  Centro C=5, Borda direita R=10

  P = [0, 1, 0, 3, 0, 5, 0, ?, ?, ?, ?]

Para i=7:
  Espelho de i em relacao a C:  espelho = 2*C - i = 2*5 - 7 = 3
  P[espelho] = P[3] = 3

  i esta dentro da borda R (i < R=10)
  Logo: P[i] >= min(P[espelho], R - i) = min(3, 10-7) = 3

  Diagrama:
  # a # b # a # b # a #
  0 1 2 3 4 5 6 7 8 9 10
          |<--- C=5 --->|  R=10
      |esp|     |  i  |
      3         7

  O palindromo ao redor de i=7 espelha o palindromo ao redor de i=3
  (ambos estao dentro do palindromo grande centrado em C=5)

  P[7] comeca com 3 e tenta expandir alem (mas nao consegue)
  P[7] = 3

Se P[i] + i > R, atualizamos C=i e R=P[i]+i (nova fronteira)
```

### Trace Completo

```
Texto original: "abaaba"
Transformada T: "#a#b#a#a#b#a#"
                 0 1 2 3 4 5 6 7 8 9 10 11 12

C=0, R=0

i=1: R=0, i>=R -> expande manualmente
     T[0]=='#'==T[2]? sim  -> P[1]=1
     T[-1]? nao            -> P[1]=1
     C=1, R=2

i=2: espelho=0, min(P[0], R-2)=min(0,0)=0
     expande: nada          -> P[2]=0

i=3: i>R=2 -> expande manualmente
     T[2]=='#'==T[4]? sim  -> P[3]=1
     T[1]=='a'==T[5]? sim  -> P[3]=2
     T[0]=='#'==T[6]? sim  -> P[3]=3
     T[-1]? nao            -> P[3]=3
     C=3, R=6

i=4: espelho=2, min(P[2], R-4)=min(0,2)=0
     expande: nada          -> P[4]=0

i=5: espelho=1, min(P[1], R-5)=min(1,1)=1
     T[3]=='b'==T[7]? nao  -> P[5]=1
     (nao atualiza C,R pois 5+1=6=R)

i=6: espelho=0, min(P[0], R-6)=min(0,0)=0
     expande: T[5]=='a'==T[7]? sim  -> P[6]=1
     T[4]=='#'==T[8]? sim          -> P[6]=2
     T[3]=='b'==T[9]? sim          -> P[6]=3
     T[2]=='#'==T[10]? sim         -> P[6]=4
     T[1]=='a'==T[11]? sim         -> P[6]=5
     T[0]=='#'==T[12]? sim         -> P[6]=6
     C=6, R=12

...continuando...

P = [0, 1, 0, 3, 0, 1, 6, 1, 0, 3, 0, 1, 0]

Maior P[i] = 6, na posicao 6
Palindromo na string original: centro = (6-1)/2 = 2 (... nao, melhor calcular)
  inicio_original = (6 - P[6]) / 2 = (6 - 6) / 2 = 0
  comprimento = P[6] = 6
  palindromo = "abaaba"
```

## Complexidade

| Caso       | Tempo | Espaco |
|------------|-------|--------|
| Melhor     | O(n)  | O(n)   |
| Medio      | O(n)  | O(n)   |
| Pior       | O(n)  | O(n)   |

A borda direita R nunca diminui e avanca no maximo n vezes no total. Cada posicao e visitada no maximo uma vez na expansao, garantindo O(n) amortizado. O espaco O(n) e para a string transformada e o array P.

## Implementacao em Rust

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

## Exemplo de Execucao

```
Texto: "abaaba"

Maior palindromo: "abaaba" (posicao 0, comprimento 6)

Todos os palindromos (comprimento >= 2):
  posicao 0: "aba"
  posicao 0: "abaaba"
  posicao 2: "aa"
  posicao 3: "aba"

Mais exemplos:
  "racecar" -> "racecar" (pos 0)
  "babad" -> "bab" (pos 0)
  "cbbd" -> "bb" (pos 1)
  "forgeeksskeegfor" -> "geeksskeeg" (pos 3)
```

Visualizacao dos palindromos em "abaaba":

```
a b a a b a
0 1 2 3 4 5

Palindromos encontrados:
  [a b a] . . .       "aba"  (centro=1, raio=1)
  [a b a a b a]       "abaaba" (centro=2.5, raio=3)
  . . [a a] . .       "aa"   (centro=2.5, raio=1)
  . . . [a b a]       "aba"  (centro=4, raio=1)
```

## Variacoes e Otimizacoes

### 1. Abordagem O(n^2): Expandir ao Redor do Centro (para Comparacao)

```rust
/// 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,
    )
}
```

### 2. Contar Total de Substrings Palindromicas

```rust
/// 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)
}
```

### 3. Palindromos em Posicoes Especificas

```rust
/// 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
}
```

## Aplicacoes Praticas

### Verificador de Palindromos em Texto Natural

```rust
/// 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);
}
```

## Comparacao com Outros Algoritmos

| Algoritmo              | Tempo   | Espaco | Encontra            |
|------------------------|---------|--------|---------------------|
| Forca Bruta            | O(n^3)  | O(1)   | Maior palindromo    |
| Expandir do Centro     | O(n^2)  | O(1)   | Maior palindromo    |
| DP (tabela)            | O(n^2)  | O(n^2) | Todos palindromos   |
| **Manacher**           |**O(n)** |**O(n)**| **Todos palindromos**|
| Eertree/Palindromic Tree| O(n)   | O(n)   | Palindromos distintos|
| Suffix Array + LCP     | O(n*log n)| O(n) | Maior palindromo    |

O Manacher e a solucao otima para palindromos em uma string, com O(n) tanto em tempo quanto em espaco. Para palindromos em streams ou textos dinamicos, a Eertree (arvore palindromica) pode ser mais adequada.

## Exercicios Praticos

1. **Menor insercoes para palindromo**: Dado um texto, encontre o menor numero de caracteres que devem ser inseridos para torna-lo um palindromo. Use Manacher para identificar o maior prefixo/sufixo palindromico.

2. **Palindromos distintos**: Conte quantos palindromos **distintos** existem como substrings de um texto. Combine Manacher com um HashSet.

3. **Particao palindromica otima**: Dado um texto, encontre o menor numero de cortes para particiona-lo em substrings que sao todas palindromos. Combine Manacher com programacao dinamica.

4. **Palindromos em duas dimensoes**: Dada uma matriz de caracteres, encontre o maior subretangulo cujas linhas E colunas sao todas palindromos. Aplique Manacher em cada dimensao.

## Veja Tambem

- [String na Biblioteca Padrao](/stdlib/string/) -- manipulacao de strings em Rust
- [Vec: Vetores Dinamicos](/stdlib/vec/) -- armazenamento do array P
- [Slices em Rust](/stdlib/slice/) -- fatias para manipulacao eficiente de bytes
- [Distancia de Levenshtein](/algoritmos/levenshtein/) -- outra abordagem para similaridade de strings
- [Suffix Array](/algoritmos/suffix-array/) -- alternativa para encontrar palindromos via LCP