LCS: Longest Common Subsequence

Цели урока

• Понимать разницу между subsequence и substring
• Выводить рекурсивную формулу LCS
• Реализовать DP решение O(mn)
• Оптимизировать память до O(n)
• Восстанавливать саму LCS, не только длину

Предварительные знания

• Динамическое программирование
• Рекурсия

• Динамическое программирование

Каждый раз когда вы делаете git diff, работает алгоритм на основе LCS. Биоинформатики используют LCS для сравнения геномов. Это один из самых практичных алгоритмов DP.

• git diff, patch: сравнение версий
• BLAST: поиск похожих генов
• Антиплагиат: сравнение текстов
• IDE: умный diff и merge

История LCS

Проблема LCS была сформулирована в 1970-х. Алгоритм Хиршберга (1975) позволяет восстановить LCS за O(n) памяти. Алгоритм Майерса (1986) используется в git для эффективного diff.

Что такое подпоследовательность?

**Подпоследовательность (subsequence)** - символы в том же порядке, но не обязательно подряд. **Подстрока (substring)** - символы подряд.

**Не путать!** LCS ≠ Longest Common Substring. Substring требует непрерывность, Subsequence - нет.

Рекурсивное решение

**Рекурсивная формула:** сравниваем последние символы.

**O(2^(m+n))** - экспоненциально! Для строк длины 20 - миллионы вызовов.

DP решение: таблица

**Запоминаем результаты подзадач в таблице.** dp[i][j] = LCS для X[0..i-1] и Y[0..j-1].

**Восстановление самой подпоследовательности:**

Оптимизация памяти

**Для вычисления dp[i] нужен только dp[i-1].** Храним две строки вместо всей таблицы.

**Компромисс:** при оптимизации памяти теряем возможность восстановить саму LCS (только длину).

Применения LCS

**LCS - фундаментальный алгоритм с множеством применений.**

• **diff/patch**: сравнение файлов (git diff)
• **Биоинформатика**: выравнивание ДНК/белков
• **Плагиат**: определение похожих текстов
• **Автодополнение**: spell checking
• **Edit Distance**: минимальные изменения (следующий урок)

**Связь с Edit Distance:**

**LeetCode:** #1143 (LCS), #583 (Delete Operation for Two Strings), #712 (Minimum ASCII Delete Sum)

LCS

• Subsequence сохраняет порядок, но не непрерывность
• Рекурсия: совпадает → +1 и оба назад; не совпадает → max двух веток
• DP таблица: O(mn) время и память
• Оптимизация: O(n) память, но теряем восстановление
• Основа для diff, биоинформатики, edit distance

Связанные темы

LCS - часть семейства задач на последовательности.

• Edit Distance — Расширение с заменами
• LIS — Похожая DP структура
• DP основы — Базовая парадигма

Связанные уроки

• alg-21-dp — LCS - канонная 2D-таблица динамического программирования
• alg-31-edit-distance — LCS напрямую ведёт к расстоянию редактирования
• alg-29-lis — LIS сводится к LCS массива и его сортированной копии
• dm-22 — Выравнивание последовательностей в биоинформатике - вариант LCS
• ml-36-seq2seq