Sequências e cadeias de matrizes

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.

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}$:

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.

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

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.

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

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<int>(a.size()), m = static_cast<int>(b.size());
    std::vector<std::vector<int>> d(n + 1, std::vector<int>(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$.

A última multiplicação divide a cadeia depois de algum $k$. Se um dos lados não estivesse parentizado de forma ótima, substituí-lo por um melhor preservaria as dimensões e reduziria o total. Avaliar todos os $k$ encontra a melhor divisão.

Preenche por comprimento crescente do intervalo. Guardar $K[i,j]$, o $k$ vencedor, permite reconstruir recursivamente os parênteses.

Para $A:5\times10$, $B:10\times3$, $C:3\times12$:

• $M[A,B]=5\cdot10\cdot3=150$.
• $M[B,C]=10\cdot3\cdot12=360$.
• Dividir $A\mid BC$ dá $0+360+5\cdot10\cdot12=960$.
• Dividir $AB\mid C$ dá $150+0+5\cdot3\cdot12=330$.

Escolhemos $(AB)C$, custo 330, e não $A(BC)$, custo 960. A resposta da tabela é um plano de cálculo; a tabela não calcula os elementos do produto.

Há $\Theta(n^2)$ intervalos e até $O(n)$ divisões por intervalo, portanto $O(n^3)$ tempo e $O(n^2)$ espaço. Com uma matriz o custo é zero. Dimensões incompatíveis tornam a cadeia inválida antes de procurar uma parentização.