1/**
2 * Наибольшая общая подпоследовательность (LCS).
3 */
4function longestCommonSubsequence(a: string, b: string): { length: number; subsequence: string } {
5  const n = a.length, m = b.length;
6  const dp: number[][] = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));
7  for (let i = 1; i <= n; i++) {
8    for (let j = 1; j <= m; j++) {
9      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]);
10    }
11  }
12  const seq: string[] = [];
13  let i = n, j = m;
14  while (i > 0 && j > 0) {
15    if (a[i - 1] === b[j - 1]) { seq.push(a[i - 1]); i--; j--; }
16    else if (dp[i - 1][j] >= dp[i][j - 1]) i--; else j--;
17  }
18  seq.reverse();
19  return { length: dp[n][m], subsequence: seq.join('') };
20}
21
22// Примеры 
23longestCommonSubsequence('hish', 'fish') // length -> 3, subsequence -> 'ish'
24longestCommonSubsequence('blue', 'clues') // length -> 3, subsequence -> 'lue'
25longestCommonSubsequence('AGGTAB', 'GXTXAYB') // length -> 4, subsequence -> 'GTAB'