1. Идея

Нужно найти любую наибольшую общую подпоследовательность двух строк s и t.

Подпоследовательность — это символы, выбранные в том же порядке, но не обязательно подряд. Значит, задача не про отрезки строки, а именно про выбор некоторых позиций.

Классический подход здесь — динамическое программирование.

Будем хранить в таблице dp[i][j] длину наибольшей общей подпоследовательности суффиксов:

• строки s, начиная с позиции i,
• строки t, начиная с позиции j.

После того как длины посчитаны, можно восстановить один из оптимальных ответов, двигаясь по таблице.

2. Наблюдения

Наблюдение 1

Если s[i] == t[j], то этот символ можно взять в общую подпоследовательность.

Тогда:

• первый символ ответа на этих суффиксах — это s[i],
• дальше остаётся решить ту же задачу для позиций i + 1 и j + 1.

Значит:

dp[i][j] = 1 + dp[i + 1][j + 1]

Наблюдение 2

Если s[i] != t[j], то одновременно взять оба этих символа нельзя.

Тогда один из них нужно пропустить:

• либо пропустить s[i] и перейти к dp[i + 1][j],
• либо пропустить t[j] и перейти к dp[i][j + 1].

Берём лучший вариант:

dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])

Наблюдение 3

Если хотя бы одна строка закончилась, то общей подпоследовательности больше быть не может.

Поэтому:

• dp[n][j] = 0 для всех j,
• dp[i][m] = 0 для всех i.

Здесь n = len(s), m = len(t).

Наблюдение 4

Одной длины недостаточно: по условию нужно вывести саму подпоследовательность. Но если таблица dp уже построена, восстановление делается жадным проходом:

• если s[i] == t[j], добавляем этот символ в ответ;
• иначе идём туда, где значение dp не меньше.

Так мы не потеряем оптимальную длину.

3. Алгоритм

Пусть n = |s|, m = |t|.

Шаг 1. Строим таблицу dp

Создаём массив dp размера (n + 1) x (m + 1) и заполняем его нулями.

Далее идём с конца строк к началу:

• для i от n - 1 до 0,
• для j от m - 1 до 0.

Переходы:

• если s[i] == t[j], то dp[i][j] = 1 + dp[i + 1][j + 1];
• иначе dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]).

Шаг 2. Восстанавливаем ответ

Запускаем два указателя:

• i = 0,
• j = 0.

Пока i < n и j < m:

• если s[i] == t[j], добавляем s[i] в ответ и увеличиваем оба указателя;
• иначе сравниваем dp[i + 1][j] и dp[i][j + 1]:
  • если dp[i + 1][j] >= dp[i][j + 1], увеличиваем i;
  • иначе увеличиваем j.

Полученная строка и будет одной из наибольших общих подпоследовательностей.

4. Почему это работает

Докажем корректность идеи по частям.

Почему правильно считается dp

Рассмотрим значение dp[i][j], то есть ответ для суффиксов s[i:] и t[j:].

Случай 1: s[i] == t[j]

Тогда можно взять этот символ в общую подпоследовательность. После этого остаётся найти оптимальный ответ для хвостов s[i+1:] и t[j+1:].

Значит, длина равна:

1 + dp[i + 1][j + 1]

Это корректно, потому что выбранный символ одинаков в обеих строках и стоит в начале рассматриваемых суффиксов.

Случай 2: s[i] != t[j]

Тогда нельзя одновременно использовать оба текущих символа как следующий символ общей подпоследовательности.

Значит, в любом оптимальном ответе обязательно:

• либо не используется s[i],
• либо не используется t[j].

То есть оптимальный ответ совпадает с лучшим из двух вариантов:

• dp[i + 1][j],
• dp[i][j + 1].

Следовательно:

dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])

Так мы перебираем все необходимые возможности и не упускаем оптимум.

Почему восстановление даёт правильный ответ

Во время восстановления мы всегда находимся в клетке dp[i][j], которая хранит длину оптимального ответа для текущих суффиксов.

• Если s[i] == t[j], то этот символ может быть первым символом оптимальной подпоследовательности, и переход в dp[i + 1][j + 1] сохраняет оптимальность.
• Если символы не равны, то:
  • если dp[i + 1][j] >= dp[i][j + 1], можно безопасно пропустить s[i];
  • иначе безопасно пропустить t[j].

В обоих случаях мы переходим в состояние, где длина оптимального ответа не уменьшается по сравнению с тем, что ещё нужно набрать.

Значит, собранная строка имеет длину dp[0][0] и является наибольшей общей подпоследовательностью.

5. Сложность

Таблица dp имеет (n + 1) * (m + 1) клеток, и каждая заполняется за O(1).

Поэтому:

• время: O(n * m)
• память: O(n * m)

При ограничениях |s|, |t| <= 1000 это подходит.

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    string s, t;
    cin >> s >> t;

    int n = (int)s.size();
    int m = (int)t.size();

    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = n - 1; i >= 0; --i) {
        for (int j = m - 1; j >= 0; --j) {
            if (s[i] == t[j]) {
                dp[i][j] = 1 + dp[i + 1][j + 1];
            } else {
                dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]);
            }
        }
    }

    string ans;
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (s[i] == t[j]) {
            ans += s[i];
            ++i;
            ++j;
        } else if (dp[i + 1][j] >= dp[i][j + 1]) {
            ++i;
        } else {
            ++j;
        }
    }

    cout << ans << "\n";
    return 0;
}

7. Код на Python 3

s = input().strip()
t = input().strip()

n = len(s)
m = len(t)

dp = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(n - 1, -1, -1):
    for j in range(m - 1, -1, -1):
        if s[i] == t[j]:
            dp[i][j] = 1 + dp[i + 1][j + 1]
        else:
            if dp[i + 1][j] >= dp[i][j + 1]:
                dp[i][j] = dp[i + 1][j]
            else:
                dp[i][j] = dp[i][j + 1]

ans = []
i = 0
j = 0

while i < n and j < m:
    if s[i] == t[j]:
        ans.append(s[i])
        i += 1
        j += 1
    elif dp[i + 1][j] >= dp[i][j + 1]:
        i += 1
    else:
        j += 1

print("".join(ans))