Как найти наибольшую общую подпоследовательность (LCS)

`dp[i][j]` — длина LCS префиксов `a[:i]` и `b[:j]`: при совпадении символов берём `dp[i−1][j−1] + 1`, иначе `max(dp[i−1][j], dp[i][j−1])`. Время и память `O(n·m)`.

Восстановление ответа

Идём от dp[n][m]: если a[i−1] == b[j−1], берём символ и шагаем по диагонали, иначе переходим в соседнюю клетку (dp[i−1][j] или dp[i][j−1]) с большим значением. Символы собираются в обратном порядке.

Для "ABCBDAB" и "BDCABA" длина LCS — 4; ответов несколько, например "BCBA".

Оптимизации и нюансы

• Только длина — хватает двух строк таблицы: O(min(n, m)) памяти.
• Восстановление с линейной памятью — алгоритм Хиршберга (D&C поверх того же ДП).
• Подпоследовательность ≠ подстрока: для наибольшей общей подстроки dp[i][j] при несовпадении обнуляется, а ответ — максимум по таблице.

Где встречается

diff и системы контроля версий (Git по умолчанию использует алгоритм Майерса O((n+m)·D), где D — размер правки), сравнение ДНК-последовательностей.

Коротко для собеседования

LCS считают двумерной ДП по префиксам двух строк: совпавший символ продлевает ответ по диагонали, иначе берём лучшего из соседей. Не путайте её с общей подстрокой, где при несовпадении значение обнуляется; на LCS построены diff и расстояние редактирования без замен.