Pular para o conteúdo
</> Entendendo Algoritmos

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
}

Letras em comum lado a lado, sem buracos. Letras diferentes zeram a célula. É o exemplo do livro.