Наибольшая общая подпоследовательность
Самая длинная цепочка символов, встречающаяся в обоих словах в том же порядке.
1function lcs(a: string, b: string): number {2 const m = a.length, n = b.length3 const d: number[][] = Array.from({ length: m + 1 }, () =>4 new Array(n + 1).fill(0),5 )6 7 for (let i = 1; i <= m; i++) {8 for (let j = 1; j <= n; j++) {9 if (a[i - 1] === b[j - 1]) {10 d[i][j] = d[i - 1][j - 1] + 1 // буквы совпали — удлиняем11 } else {12 d[i][j] = Math.max(d[i - 1][j], d[i][j - 1])13 }14 }15 }16 17 return d[m][n]18}Проблема
Самая длинная цепочка символов, встречающаяся в обоих словах в том же порядке.
Что вы видите
Таблица префиксов: совпали буквы — диагональ +1, иначе максимум соседей; обратный ход даёт цепочку.
Как это работает
Родственник Левенштейна, только считает совпадения, а не правки. Обратный ход восстанавливает общую цепочку — а «вычитание» LCS из обоих файлов даёт осмысленный diff.
Пошаговый разбор
- 01
Совпало
Диагональ + 1.
- 02
Не совпало
Лучший из соседей.
- 03
Обратный ход
Сама подпоследовательность.
Complexity и ограничения
Сложность см. в шапке страницы.
Edge cases
- Пустой вход
Корректная тривиальная обработка.
- Вырожденный случай
Минимум работы — сразу ответ.
Где встречается в реальности
git diff
Общие строки — контекст, различия — правки.
Слияния
Алгоритмы merge текстов построены на LCS.
Биоинформатика
Выравнивание белковых последовательностей.
Связанные алгоритмы
«Что общего у двух строк: LCS и diff»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.