Maior Subsequência Comum (LCS - Longest Common Subsequence)

Metáfora e Motivação

Este é outro problema basilar e extremamente clássico da Programação Dinâmica. A habilidade de encontrar similaridades entre duas cadeias é usada na bioinformática (para comparar DNA) e nos sistemas de versionamento de código (o famoso git diff que roda por baixo dos panos na sua IDE avalia as intersecções de linhas de texto).

O problema formal: Dadas duas sequências \(S1\) e \(S2\) (de tamanhos \(N\) e \(M\)), qual é a maior subsequência comum aos dois? > Uma subsequência é formada ao deletar zero ou mais caracteres de uma string, mantendo a ordem relativa dos sobreviventes. > Exemplo: Para a palavra B A N A N A: B N N é uma subsequência válida. N B A não é (a ordem foi violada).

---

O Raciocínio (Top-Down Recursivo)

Tentamos responder o desafio criando regras pontuais nas bordas de trás das palavras, descendo os índices. Criamos uma função genérica DP(a, b): Qual é o LCS se avaliarmos exclusivamente apenas os primeiros a elementos da \(S1\), e os b primeiros de \(S2\)?

1. Casos Base:
   • Esgotamos o texto a ou o texto b (um deles == 0). Se uma palavra é vazia e a outra é "TESTE", o limite máximo de letras em comum que elas podem ter unidas é 0. Retorna 0!
2. As letras testadas ali nas pontas São Iguais?
   • Por exemplo: \(S1[a] == S2[b] = \mathbf{'A'}\). Sensacional! Achamos uma nova letra compatível! Garantimos universalmente 1 ponto! E então recuamos as duas strings para testarem os recheios passados: return 1 + DP(a-1, b-1).
3. São Diferentes?
   • As bordas atômicas testadas foram, digamos, S1[a] = 'A' e S2[b] = 'B'.
   • Elas não são casáveis ao mesmo instante temporal. Alguém vai ter que ser sacrificado/descartado na ponta para destrancarmos a porta. Quem recua? Não sabemos qual sacrificar irá gerar melhor lucro interno. Então abrimos e simulamos os dois universos matriciais: Testamos sacrifar o a mantendo b, e o oposto! return max(DP(a-1, b), DP(a, b-1)).

Código Expositivo: LCS em C++ com Cache

Na C++, aplicamos esse recuo estrutural com uma Memoização via Variáveis Globais (tabela), garantindo complexidade cúbica rebaixada num teto de \(\mathcal{O}(A \times B)\) para chamadas cruzadas.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <cassert>

using namespace std;

const int MAXN = 1010;
int tabelaCache[MAXN][MAXN];

string s1, s2;

// O(N * M) complexidade, pois resolvemos um retalho exato das strings 1x
int lcs(int a, int b) { 
    // 1. Caso Base
    if(a == 0 || b == 0) return 0;
    
    // 2. Transição com Cache: Se já explorei a substring em (a, b), pula fora
    if(tabelaCache[a][b] != -1) {
        return tabelaCache[a][b];
    }
    
    // 3. Simulação Condicional 
    // Subtraímos 1 dos indices por causa de base0 Arrays string!
    if(s1[a - 1] == s2[b - 1]) {
        // Iguais! Emparelhamos. Corta as pontas e soma 1.
        return tabelaCache[a][b] = 1 + lcs(a - 1, b - 1); 
    }
    
    // Diferentes! Qual lado cortar pra andar melhor na árvore vai gerar lucro?
    return tabelaCache[a][b] = max(lcs(a - 1, b), lcs(a, b - 1));
}

void executando_testes() {
    // Caso de uso:
    s1 = "ATCGAA";  // N = 6
    s2 = "XTCAAT";  // M = 6
    
    // Limpando universo do cache sempre
    memset(tabelaCache, -1, sizeof(tabelaCache));
    
    // Envolve ambas origens no talo completo (toda s1, toda s2)
    int maxSub = lcs(s1.size(), s2.size());
    
    // As convergentes seriam as subcordas TCA = TCA 
    assert(maxSub == 3); 

    // Mais um teste drástico
    s1 = "PROGRAMACAO";
    s2 = "DINAMICA";
    memset(tabelaCache, -1, sizeof(tabelaCache));
    
    // Maior seq. (I, A, M, C, A)! Exemplo: d(I)N(AM)I(C)(A) vs pro(G)(R)a(M)a(C)(A)o
    // Resposta seria AMAA (4) ? 
    // Na verdade temos P R O G R [A] [M] [A] [C] [A] O
    // e               D I N [A] [M] I [C] [A]
    assert(lcs(s1.size(), s2.size()) == 4);

    cout << "[✅] Testes Analíticos do Algoritmo LCS Top-Down aprovados!\n";
}

int main() {
    executando_testes();
    return 0;
}

O poder da Programação Dinâmica é abstrair sua dedução analítica mental num código que explora e garante sempre as colheitadas exaustivas do maior conjunto num micro-esforço.

---

Exercícios Sugeridos

Ao praticar Longest Common Subsequence, perceba que existem pequenas variações, dentre elas o Edit Distance, no qual você precisa não apenas achar o LCS, mas descobrir qual o balanço (quantas letras preciso adicionar/remover/substituir para transformar a Palavra 1 diretamente na Palavra 2). O fundamento do LCS cobre isso por inteiro com pequenos ajustes no peso do max/min.

• Tente portar a simulação para o modelo Bottom-Up com dois loops for tradicionais em C++. Preencher a matriz manualmente.
• Resolva LCS práticos clássicos como o Beecrowd / UVa listados em repositórios gerais.