Longest Common Subsequence

Пусть lcs(i, j) — это ответ для суффиксов text1[i:] и text2[j:]. Посмотрим на их первые буквы. Если они совпадают, объединим их в пару: самую длинную общую подпоследовательность, в которой эта пара не используется, можно заменить на подпоследовательность с этой парой в начале, не сократив её. Поэтому ответ — 1 + lcs(i+1, j+1).

Если буквы различаются, обе использовать нельзя: каждую из них можно сопоставить только с более поздней буквой другой строки, и пары пересекутся. Поэтому одну из них можно пропустить: ответ — max(lcs(i+1, j), lcs(i, j+1)). Если один из суффиксов пуст, у них нет общих букв, и ответ равен 0.

Алгоритм работает медленно, потому что при каждом несовпадении выполняются два вызова. Если в строках нет общих букв, при каждом вызове возникает несовпадение, пока одна из строк не закончится, а число вызовов растёт примерно как число способов чередовать две строки. Для двух строк из 20 букв это около 2.8 × 10^11 вызовов; большие тесты содержат по 1000 букв в каждой строке. При этом существует всего (n+1) × (m+1) разных пар (i, j), поэтому почти каждый вызов повторяет предыдущий.

Состояние. Пусть dp[i][j] — наибольшая общая подпоследовательность первых i букв text1 и первых j букв text2. Работа с префиксами позволяет считать, что индекс 0 обозначает пустую строку.

Рекуррентное соотношение. Сравните последние буквы двух префиксов: text1[i-1] и text2[j-1]. Если они равны, сопоставьте их: dp[i][j] = dp[i-1][j-1] + 1. Если нет, пропустите одну из них: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Это те же рассуждения, что и в рекурсии, только идущие с конца. Базовый случай: строка 0 и столбец 0 содержат 0, потому что у пустого префикса нет ничего общего ни с чем. Порядок: каждая ячейка считывает значение ячейки сверху, слева и по диагонали сверху слева, поэтому при заполнении строка за строкой, слева направо, эти значения всегда уже готовы. Ответ — dp[n][m].

Для pear и reap строка для pea имеет вид [0, 0, 1, 2, 2]. Значение в её ячейке для rea равно 2, потому что буквы a совпадают: это значение в ячейке для pe и re, равное 1, плюс один. В последней ячейке сравниваются pear и reap: буквы r и p различаются, поэтому берётся большее из значений двух соседних ячеек — 2.

В таблице (n+1) × (m+1) ячеек, и для каждой требуется постоянное количество операций: около 10^6 шагов для двух строк длиной 1000 букв. Версия рекурсии с мемоизацией заполняет те же ячейки, но глубина рекурсии достигает n + m вызовов, что приводит к переполнению стека вызовов с размером по умолчанию в таких языках, как Python.

Строка i таблицы считывает только строку i-1 и свои предыдущие ячейки. Когда строка готова, к строкам выше неё больше никогда не обращаются. Поэтому используй два массива: prev для готовой строки и cur для заполняемой строки, а после каждой строки меняй их местами. Рекуррентное соотношение и порядок остаются точно такими же.

Для общей подпоследовательности двух строк не имеет значения, какая из них первая, поэтому их можно поменять местами и обрабатывать строки вдоль более короткой. Тогда каждая строка содержит min(n, m) + 1 чисел: 1001 вместо миллиона ячеек для самых больших входных данных, при тех же 10^6 шагах работы.

Первый элемент каждой строки соответствует пустому префиксу более короткой строки, поэтому он должен оставаться равным 0. Ответ — последний элемент последней готовой строки.