extension/src/util/lcs.ts


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

export function longestCommonSubsequence(a: string, b: string) {
  const lengths: number[][] = [];
  for (let i = 0; i <= a.length; i++) {
    lengths[i] = [];
    for (let j = 0; j <= b.length; j++) {
      if (i === 0 || j === 0) {
        lengths[i][j] = 0;
      } else if (a[i - 1] === b[j - 1]) {
        lengths[i][j] = lengths[i - 1][j - 1] + 1;
      } else {
        lengths[i][j] = Math.max(lengths[i - 1][j], lengths[i][j - 1]);
      }
    }
  }
  let result = "";
  let x = a.length;
  let y = b.length;
  while (x !== 0 && y !== 0) {
    if (lengths[x][y] === lengths[x - 1][y]) {
      x--;
    } else if (lengths[x][y] === lengths[x][y - 1]) {
      y--;
    } else {
      result = a[x - 1] + result;
      x--;
      y--;
    }
  }
  return result;
}