Общие конспекты

В школе два ученика вели конспект по одному предмету, но каждый записывал только «важные» слова. В итоге у каждого получилась строка из латинских букв без пробелов.

Учитель хочет понять, насколько их конспекты похожи: какое максимальное количество букв можно прочитать в обоих конспектах в одном и том же порядке, если разрешено вычёркивать любые буквы (возможно, разные) из каждой строки.

Найдите это максимальное количество.

Формат ввода

Даны две строки s и t, каждая в отдельной строке.

Формат вывода

Выведите одно целое число — максимальную длину общей подпоследовательности строк s и t.

Ограничения

• 1 ≤ |s| ≤ 400
• 1 ≤ |t| ≤ 400
• строки состоят из строчных латинских букв a..z

Пример

Ввод:

abcbdab
bdcaba

Вывод:

4

Ключевое наблюдение: нас интересует не подстрока (не обязаны идти подряд), а подпоследовательность — можно вычёркивать буквы. Значит, решение зависит только от того, как «лучший ответ» меняется при добавлении очередной буквы в одну из строк.

Приём: динамическое программирование по префиксам. Пусть dp[i][j] — максимальная длина общей подпоследовательности для s[:i] и t[:j]. Тогда последний шаг всегда один из трёх:

• не берём s[i-1] (смотрим dp[i-1][j]),
• не берём t[j-1] (смотрим dp[i][j-1]),
• если s[i-1] == t[j-1], берём эту букву и добавляем 1 к dp[i-1][j-1].

Мини-формула (ядро перехода):

• если равны: dp[i][j] = dp[i-1][j-1] + 1
• иначе: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

План решения:

• Считать строки s, t, взять m=len(s), n=len(t).
• Создать таблицу dp размера (m+1) x (n+1) с нулями (пустая строка даёт ответ 0).
• Двойным циклом по i=1..m, j=1..n заполнить dp по формуле выше.
• Ответ — dp[m][n].
• Чтобы экономить память, можно хранить только две строки таблицы: prev (для i-1) и cur (для i).

Сложность: O(m*n) по времени (до 160000 операций при 400x400) и O(n) памяти при «двух строках».

Частая ошибка: обновлять массив «на месте» и случайно портить значение dp[i-1][j-1]. Если используешь оптимизацию памяти — считай cur[j] только из prev[...] и cur[j-1], а prev заменяй на cur только после завершения всей строки j=1..n.