---
title: "Subsequência Comum Mais Longa (LCS)"
url: "https://rustlang.com.br/algoritmos/longest-common-subsequence/"
markdown_url: "https://rustlang.com.br/algoritmos/longest-common-subsequence.MD"
description: "Implemente o algoritmo LCS em Rust com programação dinâmica: matriz DP visual, reconstrução da subsequência e aplicações em diff e bioinformática."
date: "2026-02-24"
author: "Equipe Rust Brasil"
---

# Subsequência Comum Mais Longa (LCS)

Implemente o algoritmo LCS em Rust com programação dinâmica: matriz DP visual, reconstrução da subsequência e aplicações em diff e bioinformática.


A **Subsequência Comum Mais Longa** (LCS — Longest Common Subsequence) é um dos problemas clássicos de programação dinâmica sobre strings. Dadas duas sequências, queremos encontrar a maior subsequência presente em ambas (não necessariamente contígua). O LCS é a base de ferramentas como `diff` e `git diff`, sistemas de controle de versão, comparação de DNA em bioinformática e detecção de plágio.

Nesta página, construímos a solução em Rust passo a passo: da força bruta exponencial à solução DP quadrática, com visualização completa da matriz e reconstrução da subsequência.

## O Problema

**Entrada**: Duas sequências (strings ou arrays) `X` e `Y`.

**Objetivo**: Encontrar o comprimento da maior subsequência que aparece em ambas. Uma **subsequência** mantém a ordem relativa dos elementos, mas não precisa ser contígua.

**Exemplo:**

```
X = "ABCBDAB"
Y = "BDCABA"

Subsequências comuns: "B", "BA", "BCA", "BCBA", "BDAB", ...
LCS = "BCBA" (comprimento 4)

Nota: pode haver múltiplas LCS de mesmo comprimento.
```

## Abordagem Ingênua (Força Bruta)

Geramos todas as 2^m subsequências de `X` e verificamos quais aparecem em `Y`:

```rust
/// Força bruta: encontra LCS testando todas as subsequências.
/// Complexidade: O(2^m * n) — impraticável para strings longas.
fn lcs_bruta(x: &[u8], y: &[u8], i: usize, j: usize) -> usize {
    // Caso base: uma das sequências foi esgotada
    if i == 0 || j == 0 {
        return 0;
    }

    // Se os caracteres coincidem, fazem parte da LCS
    if x[i - 1] == y[j - 1] {
        return 1 + lcs_bruta(x, y, i - 1, j - 1);
    }

    // Caso contrário, tente avançar em cada uma
    lcs_bruta(x, y, i - 1, j).max(lcs_bruta(x, y, i, j - 1))
}

fn main() {
    let x = b"ABCBDAB";
    let y = b"BDCABA";

    let resultado = lcs_bruta(x, y, x.len(), y.len());
    println!("LCS comprimento: {}", resultado); // 4
}
```

## Identificando Subestrutura Ótima

A recorrência do LCS é elegante:

```
Se X[i] == Y[j]:
    dp[i][j] = 1 + dp[i-1][j-1]        (caractere faz parte da LCS)
Senão:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])  (pula um caractere de X ou Y)

Casos base: dp[0][j] = dp[i][0] = 0
```

- **Subestrutura ótima**: a LCS de `X[1..i]` e `Y[1..j]` depende de LCS de prefixos menores.
- **Subproblemas sobrepostos**: os mesmos pares `(i, j)` são revisitados múltiplas vezes na recursão.

## Visualização da Tabela DP

Para `X = "ABCBDAB"` e `Y = "BDCABA"`:

```
          ""  B  D  C  A  B  A
      +---+---+---+---+---+---+---+
  ""  | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
      +---+---+---+---+---+---+---+
  A   | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
      +---+---+---+---+---+---+---+
  B   | 0 | 1 | 1 | 1 | 1 | 2 | 2 |
      +---+---+---+---+---+---+---+
  C   | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
      +---+---+---+---+---+---+---+
  B   | 0 | 1 | 1 | 2 | 2 | 3 | 3 |
      +---+---+---+---+---+---+---+
  D   | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
      +---+---+---+---+---+---+---+
  A   | 0 | 1 | 2 | 2 | 3 | 3 | 4 |
      +---+---+---+---+---+---+---+
  B   | 0 | 1 | 2 | 2 | 3 | 4 | 4 |
      +---+---+---+---+---+---+---+

Reconstrução (caminho de dp[7][6] até dp[0][0]):
  dp[7][6]=4: X[7]=B == Y[6]=A? Não -> max(dp[6][6], dp[7][5])
  dp[7][5]=4: X[7]=B == Y[5]=B? Sim -> diagonal, B é parte da LCS
  dp[6][4]=3: X[6]=A == Y[4]=A? Sim -> diagonal, A é parte da LCS
  dp[4][2]=1 -> ... -> dp[3][1]=1: X[3]=C == Y[1]=C? Não...
  ...continuando: LCS = "BCBA"
```

## Complexidade

| Abordagem | Tempo | Espaço | Observação |
|-----------|-------|--------|------------|
| Força Bruta | O(2^m * n) | O(m) pilha | Exponencial |
| Top-Down (Memoização) | O(m * n) | O(m * n) | m, n = comprimentos das strings |
| Bottom-Up (Tabulação) | O(m * n) | O(m * n) | Iterativo |
| Otimizado (2 linhas) | O(m * n) | O(min(m, n)) | Sem reconstrução |

## Implementação: Top-Down (Memoização)

```rust
use std::collections::HashMap;

/// LCS com memoização usando HashMap.
fn lcs_memo(
    x: &[u8],
    y: &[u8],
    i: usize,
    j: usize,
    cache: &mut HashMap<(usize, usize), usize>,
) -> usize {
    if i == 0 || j == 0 {
        return 0;
    }

    if let Some(&valor) = cache.get(&(i, j)) {
        return valor;
    }

    let resultado = if x[i - 1] == y[j - 1] {
        1 + lcs_memo(x, y, i - 1, j - 1, cache)
    } else {
        lcs_memo(x, y, i - 1, j, cache).max(lcs_memo(x, y, i, j - 1, cache))
    };

    cache.insert((i, j), resultado);
    resultado
}

fn main() {
    let x = b"ABCBDAB";
    let y = b"BDCABA";

    let mut cache = HashMap::new();
    let comprimento = lcs_memo(x, y, x.len(), y.len(), &mut cache);
    println!("Comprimento da LCS: {}", comprimento); // 4
}
```

## Implementação: Bottom-Up (Tabulação)

```rust
/// LCS com tabulação bottom-up.
/// Retorna o comprimento e a tabela DP completa.
fn lcs_tabular(x: &[u8], y: &[u8]) -> (usize, Vec<Vec<usize>>) {
    let m = x.len();
    let n = y.len();

    // Tabela (m+1) x (n+1) inicializada com zeros
    let mut dp = vec![vec![0usize; n + 1]; m + 1];

    for i in 1..=m {
        for j in 1..=n {
            if x[i - 1] == y[j - 1] {
                // Caracteres iguais: estende a LCS
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                // Caracteres diferentes: melhor entre pular um de cada
                dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            }
        }
    }

    let comprimento = dp[m][n];
    (comprimento, dp)
}

fn main() {
    let x = b"ABCBDAB";
    let y = b"BDCABA";

    let (comprimento, _dp) = lcs_tabular(x, y);
    println!("Comprimento da LCS: {}", comprimento); // 4
}
```

## Otimização de Espaço

Como cada célula `dp[i][j]` depende apenas da linha atual e da anterior, usamos duas linhas:

```rust
/// LCS com otimização de espaço: O(min(m,n)).
/// Retorna apenas o comprimento (sem reconstrução).
fn lcs_otimizado(x: &[u8], y: &[u8]) -> usize {
    // Usa a menor string como coluna para economizar espaço
    let (curto, longo) = if x.len() <= y.len() { (x, y) } else { (y, x) };
    let n = curto.len();

    let mut anterior = vec![0usize; n + 1];
    let mut atual = vec![0usize; n + 1];

    for i in 1..=longo.len() {
        for j in 1..=n {
            if longo[i - 1] == curto[j - 1] {
                atual[j] = 1 + anterior[j - 1];
            } else {
                atual[j] = anterior[j].max(atual[j - 1]);
            }
        }
        // Troca as linhas (sem cópia — apenas troca os ponteiros)
        std::mem::swap(&mut anterior, &mut atual);
        // Limpa a linha que será reescrita
        for val in atual.iter_mut() {
            *val = 0;
        }
    }

    anterior[n]
}

fn main() {
    let x = b"ABCBDAB";
    let y = b"BDCABA";

    println!("LCS (otimizado): {}", lcs_otimizado(x, y)); // 4
}
```

## Reconstruindo a Solução

Para recuperar a subsequência real (não apenas o comprimento), percorremos a tabela DP de trás para frente:

```rust
/// Reconstrói a LCS a partir da tabela DP.
fn reconstruir_lcs(dp: &[Vec<usize>], x: &[u8], y: &[u8]) -> String {
    let mut i = x.len();
    let mut j = y.len();
    let mut lcs = Vec::new();

    while i > 0 && j > 0 {
        if x[i - 1] == y[j - 1] {
            // Caractere faz parte da LCS
            lcs.push(x[i - 1]);
            i -= 1;
            j -= 1;
        } else if dp[i - 1][j] >= dp[i][j - 1] {
            // Veio de cima
            i -= 1;
        } else {
            // Veio da esquerda
            j -= 1;
        }
    }

    // A LCS foi construída de trás para frente
    lcs.reverse();
    String::from_utf8(lcs).unwrap_or_default()
}

fn main() {
    let x = b"ABCBDAB";
    let y = b"BDCABA";

    let (comprimento, dp) = lcs_tabular(x, y);
    let subsequencia = reconstruir_lcs(&dp, x, y);

    println!("Comprimento: {}", comprimento);     // 4
    println!("Subsequência: {}", subsequencia);    // BCBA
}

/// (Incluída aqui para compilação completa)
fn lcs_tabular(x: &[u8], y: &[u8]) -> (usize, Vec<Vec<usize>>) {
    let m = x.len();
    let n = y.len();
    let mut dp = vec![vec![0usize; n + 1]; m + 1];
    for i in 1..=m {
        for j in 1..=n {
            if x[i - 1] == y[j - 1] {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            }
        }
    }
    (dp[m][n], dp)
}
```

### Aplicação: diff simplificado

O LCS é a base do algoritmo `diff`. As linhas que **não** estão na LCS são as que foram adicionadas ou removidas:

```rust
/// Diff simplificado baseado em LCS.
/// Mostra linhas adicionadas (+) e removidas (-).
fn diff_simples(original: &[&str], modificado: &[&str]) {
    let m = original.len();
    let n = modificado.len();

    // Calcula LCS das linhas
    let mut dp = vec![vec![0usize; n + 1]; m + 1];
    for i in 1..=m {
        for j in 1..=n {
            if original[i - 1] == modificado[j - 1] {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            }
        }
    }

    // Reconstrói o diff
    let mut resultado = Vec::new();
    let mut i = m;
    let mut j = n;

    while i > 0 || j > 0 {
        if i > 0 && j > 0 && original[i - 1] == modificado[j - 1] {
            resultado.push(format!("  {}", original[i - 1]));
            i -= 1;
            j -= 1;
        } else if j > 0 && (i == 0 || dp[i][j - 1] >= dp[i - 1][j]) {
            resultado.push(format!("+ {}", modificado[j - 1]));
            j -= 1;
        } else {
            resultado.push(format!("- {}", original[i - 1]));
            i -= 1;
        }
    }

    resultado.reverse();
    for linha in &resultado {
        println!("{}", linha);
    }
}

fn main() {
    let original = vec!["fn main() {", "    println!(\"Olá\");", "}"];
    let modificado = vec!["fn main() {", "    let nome = \"Rust\";", "    println!(\"Olá, {}!\", nome);", "}"];

    println!("=== Diff ===");
    diff_simples(&original, &modificado);
    // Saída:
    //   fn main() {
    // - println!("Olá");
    // + let nome = "Rust";
    // + println!("Olá, {}!", nome);
    //   }
}
```

## Exercícios Práticos

1. **Todas as LCS**: Modifique a solução para encontrar **todas** as subsequências comuns mais longas (pode haver mais de uma com o mesmo comprimento).

2. **Substring Comum Mais Longa**: Em vez de subsequência (pode pular caracteres), encontre a **substring** (contígua) mais longa. Dica: `dp[i][j] = dp[i-1][j-1] + 1` apenas quando há match, senão `dp[i][j] = 0`.

3. **LCS de 3 sequências**: Estenda o algoritmo para encontrar a LCS de três strings simultaneamente. A tabela DP torna-se tridimensional.

4. **Shortest Common Supersequence**: Dadas duas strings, encontre a menor string que contém ambas como subsequência. Dica: `comprimento = m + n - LCS(m,n)`.

## Veja Também

- [String — Strings em Rust](/stdlib/string/) — manipulação de strings e bytes
- [Vec — Vetores dinâmicos](/stdlib/vec/) — estrutura base para a matriz DP
- [Slice — Fatias](/stdlib/slice/) — acesso eficiente a partes de sequências
- [Projeto: Ferramenta Diff](/projetos/diff-tool/) — aplicação prática do LCS
- [Distância de Edição (Levenshtein)](/algoritmos/edit-distance/) — problema relacionado com matriz DP similar
- [Subsequência Crescente Mais Longa](/algoritmos/longest-increasing-subsequence/) — outra variante de subsequência com DP