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

Две задачи, которые решаются одной и той же таблицей и потому разбираются вместе.

Сразу о словах, потому что их путают и теряют на этом задачу целиком:

• подстрока — идёт подряд: у слова «динамика» это «нами», но не «дика»;
• подпоследовательность — идёт в том же порядке, но с пропусками: «дика» подходит.

Наибольшая общая подстрока двух строк — другая задача с другим решением. Если в условии написано «подстрока», а вы решаете про подпоследовательность, ответ будет больше правильного.

Наибольшая общая подпоследовательность

Состояние: $d[i][j]$ — длина наибольшей общей подпоследовательности первых $i$ символов строки $a$ и первых $j$ символов строки $b$.

Переход. Смотрим на последние символы префиксов:

• если $a_i = b_j$, их выгодно взять в ответ, и $d[i][j] = d[i-1][j-1] + 1$;
• иначе хотя бы один из них в ответ не входит, и $d[i][j] = \max(d[i-1][j],\ d[i][j-1])$.

База: $d[0][j] = d[i][0] = 0$ — с пустой строкой общего ничего нет.

vector<vector<int>> d(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        d[i][j] = (a[i - 1] == b[j - 1]) ? d[i - 1][j - 1] + 1
                                         : max(d[i - 1][j], d[i][j - 1]);

Проверено: на 2000 пар строк до девяти символов совпадает с перебором всех подпоследовательностей первой строки.

Первый пункт перехода требует обоснования — «выгодно взять» звучит как жадность. Обоснование такое: если $a_i = b_j$, то существует оптимальный ответ, в котором эта пара взята. Действительно, возьмём любой оптимальный ответ; если в нём $a_i$ не использован, а какой-то $a_k$ ($k < i$) сопоставлен с $b_j$ — заменим сопоставление на $(i, j)$, длина не изменится. Это обычное доказательство обменом.

Индексы: a[i - 1] при состоянии $d[i][j]$ — потому что $i$ считает количество взятых символов, а не номер. Смещение на единицу — самая частая опечатка в этой задаче; таблица на строку и столбец больше нужна именно для того, чтобы база не требовала отдельных случаев.

Редакционное расстояние

Наименьшее число операций, превращающих одну строку в другую. Операции: вставить символ, удалить символ, заменить символ. Расстояние называют левенштейновым.

Состояние то же: $d[i][j]$ — расстояние между префиксами длины $i$ и $j$.

vector<vector<int>> d(n + 1, vector<int>(m + 1, 0));
for (int i = 0; i <= n; i++) d[i][0] = i;           // всё удалить
for (int j = 0; j <= m; j++) d[0][j] = j;           // всё вставить
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        d[i][j] = (a[i - 1] == b[j - 1])
            ? d[i - 1][j - 1]
            : 1 + min({ d[i - 1][j - 1],            // замена
                        d[i - 1][j],                // удаление
                        d[i][j - 1] });             // вставка

Проверено: совпадает с поиском в ширину по всем строкам, достижимым правками, на 400 парах строк до четырёх символов над алфавитом из двух букв.

База здесь содержательная, а не нулевая: превратить строку длины $i$ в пустую стоит $i$ удалений. Заполнить её нулями — типичная ошибка, дающая заниженный ответ.

Если операции стоят по-разному (вставка дешевле замены), меняются только слагаемые: d[i-1][j] + costDelete и так далее. Структура остаётся.

Замер и память

Обе задачи стоят $O(nm)$ времени и, если писать в лоб, $O(nm)$ памяти. Второе и есть ограничение на практике.

Замер, g++ -O2, строки по 5000 символов над алфавитом из четырёх букв: полная таблица int заняла бы 95 МБ, а решение на двух строках — 0,04 МБ и 45 мс.

Мегабайты обычно ограничены 256, так что при длинах порядка $10^4$ полная таблица уже не помещается, и экономия памяти перестаёт быть роскошью. Обратная сторона: по двум строкам не восстановить сам ответ — если просят вывести подпоследовательность, придётся либо держать таблицу целиком, либо применять приём Хиршберга с делением пополам.

Связанные постановки

условие	что считать
наибольшая общая подпоследовательность	таблица выше
наименьшее число вставок и удалений (без замены)	$n + m - 2 \cdot \text{НОП}$
наикратчайшая общая надпоследовательность	$n + m - \text{НОП}$
НОП двух перестановок	сводится к НВП за $O(n \log n)$
наибольшая общая подстрока	другая динамика: $d[i][j]$ — общий суффикс префиксов

Последняя строка — полезное упражнение на понимание: переход там короче ($d[i][j] = d[i-1][j-1] + 1$ при совпадении, иначе ноль), а ответ берётся как максимум по всей таблице, а не из угла. Обычно её решают хешами или суффиксными структурами, но динамика короче и при $nm \le 10^7$ достаточна.