Наибольшая общая подпоследовательность: таблица для двух строк

Если ты помнишь переход LCS в обе ветки и умеешь восстановить строку из таблицы, листай до «Теперь сам».

Как думаешь, чем подпоследовательность отличается от подстроки

«АЛГОРИТМ» и «ЛОГАРИФМ». Какая у них самая длинная общая ПОДСТРОКА - то есть кусок подряд? Всего два символа, «РИ»: трёхсимвольных общих кусков у них нет.

А если разрешить пропуски - брать символы в том же порядке, но не подряд? Прежде чем читать дальше, попробуй найти такую общую последовательность руками. Это и есть разница между двумя задачами, и у них разные таблицы.

На что это похоже

Сравнение двух версий документа. Редактор не ищет самый длинный одинаковый абзац - он ищет, какие строки остались НА МЕСТЕ, а какие добавлены и удалены. «Остались на месте» - это и есть общая подпоследовательность, а всё, что в неё не вошло, попадает в diff со знаками плюс и минус. Любой git diff, который ты видел, - это восстановленный ответ такой таблицы.

Механизм: состояние и две ветки перехода

СОСТОЯНИЕ
dp[i][j] = длина LCS префиксов: первых i символов строки a
           и первых j символов строки b

состояний (n+1) × (m+1), переход O(1) ⇒ цена Θ(n·m)

ПЕРЕХОД - две ветки

если a[i] == b[j]:                   символы совпали, берём оба
    dp[i][j] = dp[i−1][j−1] + 1

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

база: dp[0][j] = dp[i][0] = 0 - с пустой строкой общего ничего

ПОЧЕМУ В ПЕРВОЙ ВЕТКЕ НЕ НУЖЕН max
если символы совпали, брать их в LCS ВСЕГДА безопасно - это
обменный аргумент из раздела 14: в любом ответе, где эта пара не взята,
её можно подставить, не ухудшив длину

ВОССТАНОВЛЕНИЕ СТРОКИ: идём от dp[n][m] назад
    a[i] == b[j]          → символ в ответ, i−1, j−1
    dp[i−1][j] >= dp[i][j−1] → i−1  (иначе j−1)

Правило

Для двух последовательностей состояние - пара префиксов (i, j). У LCS переход две ветки: совпали символы - dp[i−1][j−1] + 1 без всякого максимума, не совпали - максимум из двух соседей. Цена Θ(n·m), память - та же таблица (сворачивается до двух строк, если ответ нужен только числом). Подпоследовательность идёт в том же ПОРЯДКЕ, но не обязательно подряд - этим она отличается от подстроки, у которой другая таблица и другой переход. Саму строку восстанавливают обратным проходом от правого нижнего угла; если по пути печатать не совпадения, а выкинутые символы, получается diff.

Разбор: таблица для «АЛГОРИТМ» и «ЛОГАРИФМ»

        _   Л   О   Г   А   Р   И   Ф   М
    _   0   0   0   0   0   0   0   0   0
    А   0   0   0   0   1   1   1   1   1
    Л   0   1   1   1   1   1   1   1   1
    Г   0   1   1   2   2   2   2   2   2
    О   0   1   2   2   2   2   2   2   2
    Р   0   1   2   2   2   3   3   3   3
    И   0   1   2   2   2   3   4   4   4
    Т   0   1   2   2   2   3   4   4   4
    М   0   1   2   2   2   3   4   4   5

Ответ в правом нижнем углу: 5. Разберём две клетки.

строка «Г», столбец «Г» (символы совпали):
    dp = dp[предыдущая строка][предыдущий столбец] + 1 = 1 + 1 = 2

строка «Т», столбец «И» (Т ≠ И):
    выкинуть Т → dp[строка И][столбец И] = 4
    выкинуть И → dp[строка Т][столбец Р] = 3
    max = 4 - строка «Т» просто повторяет предыдущую

Обрати внимание на строку «Т»: она целиком совпадает со строкой «И». Так и выглядит символ, которого во второй строке нет вовсе - он не добавляет ничего.

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

идём из правого нижнего угла (строка М, столбец М).
Правило: совпали символы - шаг по диагонали; иначе идём туда, где значение больше,
а при равенстве - вверх.

    М == М                      → в ответ «М», по диагонали
    Т ≠ Ф, сверху 4, слева 4    → вверх   (Т выкинута из первой строки)
    И ≠ Ф, сверху 3, слева 4    → ВЛЕВО   (Ф выкинута из второй)
    И == И                      → в ответ «И», по диагонали
    Р == Р                      → в ответ «Р», по диагонали
    О ≠ А, сверху 2, слева 2    → вверх   (О выкинута)
    Г ≠ А, сверху 1, слева 2    → ВЛЕВО   (А выкинута из второй)
    Г == Г                      → в ответ «Г», по диагонали
    Л ≠ О, сверху 0, слева 1    → ВЛЕВО   (О выкинута из второй)
    Л == Л                      → в ответ «Л», по диагонали
дошли до столбца 0 - дальше идти некуда
читаем задом наперёд: Л Г Р И М

Обрати внимание на шаги ВЛЕВО: после «вверх» мы оказываемся в другой клетке, и символы там снова могут
не совпадать - тогда делается ещё один шаг. Трасса без этих шагов выглядит короче, но она неверна:
путь обязан дойти до края таблицы.

Проверим руками: в «АЛГОРИТМ» буквы Л Г Р И М стоят на местах 2, 3, 5, 6, 8 - по возрастанию. В «ЛОГАРИФМ» - на местах 1, 3, 5, 6, 8. Порядок соблюдён в обеих, значит это общая подпоследовательность длины 5. Самая длинная общая ПОДСТРОКА у этих слов - два символа («РИ»), и разница между двумя задачами здесь видна особенно наглядно: пропуски дают выигрыш с двух до пяти.

Разбор: та же таблица - это diff

Если при обратном проходе печатать не только совпадения, а все три случая, получается список правок:

диагональ (совпало)        символ остался:       =М
шаг вверх (выкинут из a)   символ удалён:        −О
шаг влево (выкинут из b)   символ добавлен:      +А

для «АЛГОРИТМ» → «ЛОГАРИФМ» (тем же обходом, что выше):
    −А  =Л  +О  =Г  +А  −О  =Р  =И  +Ф  −Т  =М

Именно так устроены построчные diff в системах контроля версий: элементами последовательности берут не символы, а СТРОКИ файла, и LCS даёт «неизменные строки», а всё остальное - плюсы и минусы.

практический масштаб
файл в 5000 строк против файла в 5000 строк - таблица 25 миллионов клеток.
Поэтому настоящие diff-алгоритмы (Myers) считают не всю таблицу, а только
окрестность диагонали: цена O((n+m)·D), где D - размер различий.
Для похожих файлов D мал, и алгоритм линеен

Это важная практическая развилка: честная таблица Θ(n·m) - для коротких входов, а для файлов берут алгоритм, цена которого зависит от РАЗМЕРА РАЗЛИЧИЙ, а не от размера входа.

Что ломается без этого

Первое: путать подпоследовательность с подстрокой. У подстроки другой переход (dp[i][j] = длина общего окончания, и при несовпадении ставится ноль), и ответ надо искать не в углу, а максимумом по всей таблице. Второе: писать max в первой ветке - при совпадении символов максимум не нужен, и это не оптимизация, а признак непонимания: взять совпавшую пару всегда безопасно. Третье: при восстановлении идти «куда больше», не проверив совпадение символов первым: тогда на равных соседях маршрут уходит в сторону и ответ получается короче. Четвёртое: сворачивать таблицу до двух строк, а потом пытаться восстановить строку - восстановление требует всей таблицы (или приёма Хиршберга, о котором в главе про память). Пятое: применять Θ(n·m) к файлам: два файла по 100 тысяч строк - это 10^10 клеток, то есть никогда.

Зачем это в работе

LCS - это основа всего, что сравнивает две версии: git diff, diff в редакторах, подсветка изменений в документах, сравнение структур данных в тестах. Знание перехода помогает читать поведение этих инструментов: например, почему diff иногда показывает странное выравнивание - потому что оптимальных ответов несколько, и алгоритм выбрал один из равноценных. Вторая область - биоинформатика: выравнивание последовательностей ДНК и белков - это та же таблица с другими весами (алгоритмы Нидлмана-Вунша и Смита-Ватермана). Третье - нечёткий поиск и исправление опечаток, но там чаще нужна не длина общей части, а расстояние редактирования, и это следующий урок.

Теперь сам

Строки «СТРОКА» и «СТРАНА». Чему равна длина их LCS и какая это подпоследовательность?

        _   С   Т   Р   А   Н   А
    _   0   0   0   0   0   0   0
    С   0   1   1   1   1   1   1
    Т   0   1   2   2   2   2   2
    Р   0   1   2   3   3   3   3
    О   0   1   2   3   3   3   3
    К   0   1   2   3   3   3   3
    А   0   1   2   3   4   4   4