# Sequências e cadeias de matrizes LCS, distância de edição e parentização de matrizes, com tabelas e reconstrução. Página: https://resumos.rgo.pt/cadeiras/da/sequencias-dinamica/ `ABCD` e `BACD` partilham `ACD` como subsequência, conservando a ordem das letras e omitindo uma de cada palavra. Para encontrar uma subsequência comum de comprimento máximo, comparamos prefixos cada vez maiores e guardamos o melhor para cada par. A última letra de cada prefixo determina quais as células anteriores que precisamos de consultar. A distância de edição usa o mesmo par de prefixos com outro objetivo: contar operações para transformar uma palavra na outra. A cadeia de matrizes usa estados por intervalos para escolher os parênteses sem mudar a ordem dos fatores. As três técnicas separam o que já está decidido do que ainda falta decidir. ## Subsequência comum mais longa Uma subsequência conserva a ordem, mas pode omitir elementos. `ACD` é subsequência de `ABCD`; não é um subvetor contíguo. A **LCS** de duas sequências é uma subsequência comum de comprimento máximo. Define $L[i,j]$ como o comprimento da LCS dos primeiros $i$ símbolos de $X$ e dos primeiros $j$ de $Y$. Os índices $i,j$ são comprimentos, pelo que $X[i-1]$ e $Y[j-1]$ são os últimos símbolos desses prefixos. $$ L[i,j]=\begin{cases} 0,&i=0\text{ ou }j=0,\\ 1+L[i-1,j-1],&X[i-1]=Y[j-1],\\ \max(L[i-1,j],L[i,j-1]),&X[i-1]\ne Y[j-1]. \end{cases} $$ Quando os últimos símbolos coincidem, existe uma LCS que os emparelha, porque uma LCS que usasse uma ocorrência anterior pode deslocar esse emparelhamento para os últimos sem perder a ordem. Quando diferem, não podem ser os dois o último símbolo comum, por isso pelo menos um fica de fora e as duas exclusões cobrem as alternativas. Para $X=\texttt{ABCD}$ e $Y=\texttt{BACD}$: | $X\backslash Y$ | vazio | B | A | C | D | | --- | --- | --- | --- | --- | --- | | vazio | 0 | 0 | 0 | 0 | 0 | | A | 0 | 0 | 1 | 1 | 1 | | B | 0 | 1 | 1 | 1 | 1 | | C | 0 | 1 | 1 | 2 | 2 | | D | 0 | 1 | 1 | 2 | 3 | O comprimento é 3. Para reconstruir, regista em cada célula a decisão que atinge o máximo: diagonal quando $X[i-1]=Y[j-1]$, senão cima ou esquerda conforme o maior valor. Começa em $(4,4)$, onde D coincide: segue a diagonal e guarda D. Em $(3,3)$, C coincide e guarda C do mesmo modo. Em $(2,2)$, $B\ne A$ e $L[1,2]=L[2,1]=1$, um empate entre cima e esquerda: escolher cima encontra A e dá `ACD`, enquanto escolher esquerda encontra B e dá `BCD`. Inverte os símbolos guardados no fim. O empate representa várias soluções ótimas, não um erro. As duas respostas conservam a ordem em ambas as sequências e atingem o mesmo comprimento. O tempo e a tabela são $O(|X||Y|)$. Duas linhas chegam para o comprimento, mas deixam de guardar o percurso completo de reconstrução. Uma string vazia tem LCS de comprimento zero com qualquer outra. ## Distância de edição A distância de Levenshtein é o mínimo número de inserções, remoções e substituições para transformar $X$ em $Y$. Cada operação custa 1; manter um símbolo igual custa 0. Outros custos definem outro problema. Define $D[i,j]$ para os primeiros $i$ símbolos de $X$ e os primeiros $j$ de $Y$. Temos $D[i,0]=i$, porque removemos todos, e $D[0,j]=j$, porque inserimos todos. $$ D[i,j]=\min\begin{cases} D[i-1,j]+1&\text{remover }X[i-1],\\ D[i,j-1]+1&\text{inserir }Y[j-1],\\ D[i-1,j-1]+[X[i-1]\ne Y[j-1]]&\text{manter ou substituir}. \end{cases} $$ O símbolo entre parênteses retos vale 1 se a condição é verdadeira e 0 se é falsa. As três linhas são as possíveis últimas operações da transformação. Não acrescentes automaticamente 1 à diagonal quando os símbolos já são iguais. Para `canto` e `gato`, a tabela é: | $X\backslash Y$ | vazio | g | a | t | o | | --- | --- | --- | --- | --- | --- | | vazio | 0 | 1 | 2 | 3 | 4 | | c | 1 | 1 | 2 | 3 | 4 | | a | 2 | 2 | 1 | 2 | 3 | | n | 3 | 3 | 2 | 2 | 3 | | t | 4 | 4 | 3 | 2 | 3 | | o | 5 | 5 | 4 | 3 | 2 | A distância é 2. Uma transformação ótima substitui `c` por `g` e remove `n`. Guardar a operação escolhida permite reconstruir um alinhamento, incluindo inserções e remoções. O custo é $O(|X||Y|)$ tempo e espaço, ou $O(\min(|X|,|Y|))$ espaço para apenas a distância. **main.cpp** ```cpp #include #include #include #include int main() { std::string a, b; if (!std::getline(std::cin, a) || !std::getline(std::cin, b) || a.size() > 500 || b.size() > 500) { std::cout << "entrada invalida\n"; return 0; } int n = static_cast(a.size()), m = static_cast(b.size()); std::vector> d(n + 1, std::vector(m + 1)); for (int i = 0; i <= n; ++i) d[i][0] = i; for (int j = 0; j <= m; ++j) d[0][j] = j; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) d[i][j] = std::min({d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + (a[i - 1] != b[j - 1])}); std::cout << "distancia " << d[n][m] << '\n'; } ``` Devolve `distancia 2`. Lê duas linhas, por isso uma linha vazia representa uma string vazia; mudar a entrada para `\ngato` deve dar 4. O exemplo limita cada linha a 500 bytes e trata bytes como símbolos. Para texto Unicode geral, um carácter pode ocupar vários bytes; seria necessário escolher e implementar uma unidade como pontos de código ou grafemas. Distância de edição não é LCS com outra designação. Se só inserções e remoções fossem permitidas, o custo mínimo seria $|X|+|Y|-2|LCS|$. Permitir substituição a custo 1 pode baixar esse valor: `a` para `b` custa 1, e não 2. ## Cadeia de matrizes Queremos calcular $A_1A_2\cdots A_n$ com o menor número de multiplicações escalares. A ordem das matrizes permanece; mudamos apenas os parênteses. A multiplicação é associativa, mas a matriz intermédia e o custo dependem da parentização. Se $A_i$ tem dimensões $p_{i-1}\times p_i$, multiplicar uma matriz $r\times s$ por outra $s\times t$ custa $rst$ multiplicações escalares no algoritmo usual. Define $M[i,j]$ como o menor custo para a cadeia $A_i\cdots A_j$. $$ M[i,i]=0, $$ $$ M[i,j]=\min_{i\le k