Equipe Rust Brasil 9 min de leitura

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.

programação dinâmica lcs subsequência strings rust

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:

/// 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

AbordagemTempoEspaçoObservação
Força BrutaO(2^m * n)O(m) pilhaExponencial
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)

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)

/// 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:

/// 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:

/// 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:

/// 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