LCS

Subsecuencia Común Más Larga

Modo: Top-Down

Cadena 1

Cadena 2

Velocidad animación

Llenado de tabla

const lcs = (X, m, Y, n, memo) => {
if (memo[m][n] > -1) {
return memo[m][n];
} else if (m === 0 \|\| n === 0) {
memo[m][n] = 0;
} else if (X[m - 1] === Y[n - 1]) {
memo[m][n] = 1 + lcs(X, m - 1, Y, n - 1, memo);
} else {
memo[m][n] = Math.max(lcs(X, m - 1, Y, n, memo),lcs(X, m, Y, n - 1, memo));
}
return memo[m][n];
}

Obtención de LCS

while (i > 0 && j > 0) {
if (X[i - 1] === Y[j - 1]) {
lcsString = X[i - 1] + lcsString; i--; j--;
} else if (dpTable[i - 1][j] > dpTable[i][j - 1]) {
i--;
} else {
j--;
}
}