1/**
2 * Самая длинная общая подстрока (Longest Common Substring).
3 */
4function longestCommonSubstring(a: string, b: string): { length: number; substring: string } {
5  const n = a.length, m = b.length;
6  const dp: number[][] = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));
7  let maxLen = 0, endA = 0;
8  for (let i = 1; i <= n; i++) {
9    for (let j = 1; j <= m; j++) {
10      if (a[i - 1] === b[j - 1]) {
11        dp[i][j] = dp[i - 1][j - 1] + 1;
12        if (dp[i][j] > maxLen) { maxLen = dp[i][j]; endA = i; }
13      } else dp[i][j] = 0;
14    }
15  }
16  return { length: maxLen, substring: a.slice(endA - maxLen, endA) };
17}
18
19// Примеры
20longestCommonSubstring('hish', 'fish') // length -> 3, substring -> 'ish'
21longestCommonSubstring('blue', 'clues') // length -> 3, substring -> 'lue'
22longestCommonSubstring('ABABC', 'BABCA') // length -> 4, substring -> 'BABC'