Longest Common Subsequence Algoritması

1function lcs(a: string, b: string): string {
2  const dp = Array.from({ length: a.length + 1 }, () => Array(b.length + 1).fill(0));
3  for (let i = 1; i <= a.length; i += 1) {
4    for (let j = 1; j <= b.length; j += 1) {
5      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]);
6    }
7  }
8  let i = a.length, j = b.length;
9  const result: string[] = [];
10  while (i > 0 && j > 0) {
11    if (a[i - 1] === b[j - 1]) {
12      result.unshift(a[i - 1]);
13      i -= 1; j -= 1;
14    } else if (dp[i - 1][j] >= dp[i][j - 1]) {
15      i -= 1;
16    } else {
17      j -= 1;
18    }
19  }
20  return result.join('');
21}