Calculadora LCS

O problema da subsequência comum mais longa pede a sequência de caracteres mais longa que aparece na mesma ordem em duas strings de entrada, sem exigir contiguuidade. É a base de programação dinâmica das ferramentas de diff por linhas, ajudas de merge em controle de versão, detectores de plágio que toleram reordenações ruidosas e a comparação de sequências biológicas quando inserções e exclusões importam mais do que um substring exato. Esta calculadora de subsequência comum mais longa aceita duas strings, preenche uma tabela clássica de comprimentos em tempo linear em relação ao produto dos comprimentos, reconstrói um LCS válido por backtracking e devolve tanto o comprimento numérico quanto a string da subsequência. Entradas vazias são válidas e produzem comprimento zero.

O que é (e o que não é) uma subsequência comum mais longa

Uma subsequência de uma string é qualquer string obtida ao apagar zero ou mais caracteres sem reordenar os que restam. Uma subsequência comum de duas strings é uma string que é subsequência de ambas. Uma subsequência comum mais longa, ou LCS, é qualquer subsequência comum cujo comprimento é máximo entre todas as subsequências comuns.

Diferente de um substring comum mais longo, um LCS não precisa ocupar um bloco contíguo em nenhuma das entradas: o par clássico ABCBDAB e BDCABA admite várias strings LCS de comprimento quatro, como BCBA e BDAB, conforme os empates que a reconstrução escolhe. Algoritmos de diff e ferramentas de alinhamento de DNA se apoiam nessa noção não contígua porque edições reais inserem e removem símbolos em vez de apenas deslizar uma janela fixa.

O comprimento de um LCS é uma pontuação de similaridade útil; os caracteres reconstruídos servem quando você quer um esqueleto de alinhamento explícito ao lado da pontuação. Não devolve todos os LCS possíveis, scripts de edição nem percentuais de similaridade—esses são problemas separados construídos sobre a mesma ideia de tabela DP.

Onde a subsequência comum ajuda de verdade

Cursos de ciência da computação e juízes online precisam de um oráculo de referência que devolva um comprimento correto e uma subsequência válida para strings curtas arbitrárias sem que alunos colem soluções em um IDE completo. Recursos de produto próximos ao diff—resumos de mudança, dicas de conflito de merge, alinhamento de linhas de log—muitas vezes querem o comprimento LCS como sinal barato de similaridade antes de um passe mais pesado de distância de edição.

Demos didáticas de bioinformática usam strings do alfabeto DNA de brinquedo (A, C, G, T) para mostrar como inserções e exclusões ainda deixam um esqueleto compartilhado longo. Mantenha as strings abaixo do limite de comprimento, fixe a subsequência reconstruída nos testes se importar qual de várias respostas igualmente longas você obtém, e terá resultados LCS reproduzíveis sem montar uma biblioteca numérica própria.