# Maior subsequência comum

O problema da maior subsequência comum(LCS) é sobre achar a maior subsequência em todas as sequências em um conjunto de sequências(normalmente duas). O problema da maior subsequência comum é um clássico da ciência da computação, é a base de programas de comparação de dados como o diff, e tem aplicações em computação linguística e bioinformática. Também é amplamente usado em sistemas de versionamento como Git para mesclar múltiplas mudanças feitas em arquivos.
Por exemplo, considere as sequências $ABCD$ e $ACBAD$. Ambos têm 5 subsequências comuns de tamanho 2: $AB$, $AC$, $BD$ e $CD$; e 2 subsequências comuns de tamanho 3: $ABD$ e $ACD$. Então $ABD$ e $ACD$ são as maiores subsequências comuns.

## Complexidade

Para os casos gerais de um número arbitrário de sequências, o problema é NP-difícil(veja complexidade de tempo). E quando o número de sequências é constante, pode ser resolvido em tempo polinomial com uso da programação dinâmica.
Dado $N$ sequências de tamanho $n_{1},...,n_{N}$, uma pesquisa pode testar cada uma das $2^{n_{1}}$ subsequências da primeira sequência para determinar se é também subsequência das sequências restantes; cada subsequência pode ser testada em tempo linear nos tamanhos das sequências, então o tempo para isso seria:
$O\left(2^{n_{1}}\sum _{i>1}n_{i}\right)$
Para o caso das 2 sequências de $n$ e $m$ elementos, o tempo de processamento usando a programação dinâmica seria $O(nm)$. Para um número arbitrário de sequências, a programação dinâmica nos daria a solução em
$O\left(N\prod _{i=1}^{N}n_{i}\right)$
Existem métodos com menor complexidade, que geralmente necessitam do tamanho do LCS, ou tamanho do alfabeto quando não ambos.
O LCS não é necessariamente exclusivo; no pior caso, o número de subsequências comuns é exponencial nos tamanhos das sequências, então a complexidade deve ser pelo menos exponencial.

## Solução para duas sequências

O problema LCS tem uma estrutura ideal: o problema pode ser quebrado em partes menores; problemas mais simples, que podem ser quebrados em menores; e então, a solução se torna trivial. O LCS em particular permite que soluções complexas possam ser quebradas em soluções mais simples e reutilizáveis. Problemas com essas características podem ser abordados com a programação dinâmica, em que as soluções para problemas menores podem ser memorizadas e reutilizadas

### Prefixos

O prefixo $S_{n}$ de $S$ é definido como os $n$ primeiros caracteres de $S$. Por exemplo, os prefixos de $S=AGCA$ são:
$S_{0}={\text{nenhum}}$
$S_{1}=A$
$S_{2}=AG$
$S_{3}=AGC$
$S_{4}=AGCA$
Considere que $LCS(X,Y)$ seja uma função que compute a maior subsequência comum de $X$ e $Y$. Esta função tem duas propriedades muito interessantes.

### Primeira propriedade

$LCS(X{\hat}A,Y{\hat}A)=LCS(X,Y){\hat}A$, para todas as strings $X$, $Y$ e todos os símbolos $A$, onde '^' representa a concatenação de strings. Isso permite simplificar o processo de LCS para as duas sequências que terminam com o mesmo símbolo. Por exemplo, LCS("BANANA","ATANA") = LCS("BANAN","ATAN")^A, continuam com o mesmo símbolo comum, LCS("BANANA","ATANA") = LCS("BAN","AT")^"ANA".

### Segunda propriedade

Se $A$ e $B$ são símbolos distintos ($A\neqB$), então $LCS(X{\hat}A,Y{\hat}B)$ é uma das strings de tamanho máximo no conjunto $\{LCS(X{\hat}A,Y),LCS(X,Y{\hat}B)\}$, para todas as strings $X$, $Y$.
Por exemplo, LCS ("ABCDEFG", "BCDGK") é a sequência mais longa de <mathLCS ("ABCDEFG", "BCDG") e LCS ("ABCDEF", "BCDGK"); se ambos tivessem o mesmo comprimento, um deles poderia ser escolhido arbitrariamente.
Para prosseguir, diferencie os dois casos:
Se LCS ("ABCDEFG", "BCDGK") termina com um "G", então o "K" final não pode estar no LCS, portanto LCS ("ABCDEFG", "BCDGK") = LCS ("ABCDEFG", "BCDG ").
Se LCS ("ABCDEFG", "BCDGK") não terminar com um "G", então o "G" final não pode estar no LCS, portanto, LCS ("ABCDEFG", "BCDGK") = LCS ("ABCDEF", "BCDGK").

### Definição da função

Considere duas sequências definidas da seguinte forma: $X=(x_{1},X_{2},...,X_{m})$ e $Y=(Y_{1},Y_{2},...,Y_{n})$. Os prefixos de $X$ são $X_{1},X_{2},...,m$; os prefixos de $Y$ são $Y_{1},Y_{2},...,n$. Considere que $LCS(X_{i},Y_{j})$ represente o conjunto das maiores subsequências comuns dos prefixos $X_{i}$ e $Y_{j}$. Esse conjunto de subsequências é dado por:
${\displaystyle {\mathit {LCS}}(X_{i},Y_{j})={\begin{cases}\emptyset &{\mbox{se }}i=0{\mbox{ ou }}j=0\\{\mathit {LCS}}(X_{i-1},Y_{j-1}){\hat}x_{i}&{\mbox{se }}i,j>0{\mbox{ e }}x_{i}=y_{j}\\\operatorname {\max } \{{\mathit {LCS}}(X_{i},Y_{j-1}),{\mathit {LCS}}(X_{i-1},Y_{j})\}&{\mbox{se }}i,j>0{\mbox{ e }}x_{i}\neq y_{j}\end{cases}}}$
Para achar o LCS de $X_{i}$ e $Y_{j}$, compare $x_{i}$ e $y_{j}$. Se forem iguais, então a sequência $LCS(X_{i-1},Y_{j})$ é estendida pelo elemento $x_{i}$. Se não forem iguais, então a mais longa das duas sequências, $LCS(X_{i},Y_{j-1})$ e $LCS(X_{i-1},Y_{j})$ é retida. (Se forem do mesmo tamanho mas não idênticas, ambas serão retidas)
* ↑ David Maier (1978). «The Complexity of Some Problems on Subsequences and Supersequences». ACM Press. J. ACM. 25 (2): 322–336. doi:10.1145/322063.322075
* ↑ L. Bergroth and H. Hakonen and T. Raita (2000). «A Survey of Longest Common Subsequence Algorithms». IEEE Computer Society. SPIRE. 00: 39–48. ISBN 0-7695-0746-8. doi:10.1109/SPIRE.2000.878178
* ↑ Xia, Xuhua (2007). Bioinformatics and the Cell: Modern Computational Approaches in Genomics, Proteomics and Transcriptomics. New York: Springer. p. 24. ISBN 978-0-387-71336-6