阅读中文版本

LCS CLI

A Node CLI that computes the longest common subsequence of two strings from argv using dynamic programming and prints the LCS and its length.

node --version

node lcs.mjs ABCBDAB BDCAB

node --test lcs.test.mjs

Prints the longest common subsequence of the two input strings and its length, using a dynamic programming table.

What it does

Builds a dynamic programming table where dp[i][j] is the LCS length of the first i and first j characters, then backtracks to reconstruct the subsequence. The table is O(m*n) in space and time.

const [a, b] = [process.argv[2], process.argv[3]];
const m = a.length, n = b.length;
const dp = Array.from({length: m + 1}, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) for (let j = 1; j <= n; j++)
  dp[i][j] = a[i-1] === b[j-1] ? dp[i-1][j-1] + 1 : Math.max(dp[i-1][j], dp[i][j-1]);
let i = m, j = n, lcs = '';
while (i > 0 && j > 0) {
  if (a[i-1] === b[j-1]) { lcs = a[i-1] + lcs; i--; j--; }
  else if (dp[i-1][j] > dp[i][j-1]) i--; else j--;
}
console.log(lcs + ' (length ' + dp[m][n] + ')');

Run and verify

node lcs.mjs ABCBDAB BDCAB

Run the test command to check the implementation: node --test lcs.test.mjs.

Expected Output

For the strings ABCBDAB and BDCAB, one longest common subsequence is BCAB with length 4:

BCAB (length 4)

Limitations

The DP table uses O(m*n) space, which is large for very long strings. A space-optimized version using two rows would reduce space to O(min(m,n)) but cannot reconstruct the subsequence.