Subcadeia comum
Outra aplicação da programação dinâmica: comparar duas palavras. Cada célula da tabela compara uma letra de cada palavra e reaproveita respostas anteriores. É a ideia por trás de corretores ortográficos e da comparação de DNA.
Explicação do algoritmo: escolha um nível para ler.
{ }Ver o código
// consecutiva = true: subcadeia (sem buracos); false: subsequência
function subcadeiaComum(a, b, consecutiva) {
const t = Array.from({ length: a.length }, () => Array(b.length).fill(0));
const celula = (i, j) => (i < 0 || j < 0 ? 0 : t[i][j]);
let maior = 0;
for (let i = 0; i < a.length; i++) {
for (let j = 0; j < b.length; j++) {
if (a[i] === b[j]) {
t[i][j] = celula(i - 1, j - 1) + 1; // letras iguais: diagonal + 1
} else {
t[i][j] = consecutiva
? 0 // quebrou a sequência
: Math.max(celula(i - 1, j), celula(i, j - 1)); // herda o melhor vizinho
}
maior = Math.max(maior, t[i][j]);
}
}
return consecutiva ? maior : celula(a.length - 1, b.length - 1); // tamanho da resposta
}