kz-maxx

RU KZ
← Главная

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

LCS: динамическое программирование по двум строкам

Что такое LCS?

LCS — это Longest Common Subsequence. По-русски: наибольшая общая подпоследовательность.

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

Подпоследовательность — это не обязательно подряд. Можно пропускать символы, но нельзя менять порядок.

Пример

Даны строки: 

s = "abcde"
t = "ace"

Общая подпоследовательность: 

ace

Ответ: 

3

Потому что длина строки "ace" равна 3.

Подпоследовательность и подстрока

Термин Что значит Пример
Подпоследовательность можно пропускать символы "ace" из "abcde"
Подстрока символы идут подряд "bcd" из "abcde"
LCS — это именно подпоследовательность, а не подстрока.

Главная идея DP

Пусть: 

dp[i][j]

Это длина LCS для первых i символов строки s и первых j символов строки t.

dp[i][j] = ответ для s[0..i-1] и t[0..j-1]

Почему индексы i и j?

У нас две строки, поэтому состояние зависит от двух параметров:

  • i — сколько символов взяли из первой строки
  • j — сколько символов взяли из второй строки
s = abcde
t = ace

dp[3][2] = ответ для "abc" и "ac"

Базовые значения

Если одна из строк пустая, общая подпоследовательность имеет длину 0. 

dp[0][j] = 0;
dp[i][0] = 0;

В C++ глобальный массив автоматически заполнен нулями.

Переход DP

Смотрим последние символы: 

s[i - 1]
t[j - 1]

Если они равны, значит этот символ можно добавить в ответ: 

if (s[i - 1] == t[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + 1;
}

Если они разные, то пробуем убрать один символ: 

else {
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}

Формула целиком

if (s[i - 1] == t[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
символы равны → берем этот символ
символы разные → выбираем лучший из двух вариантов

Задача 1: найти длину LCS

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

Input

abcde
ace

Output

3

Полная реализация длины LCS

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

string s, t;
int dp[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s >> t;

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

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

    cout << dp[n][m];

    return 0;
}

Как читать dp[n][m]?

Если: 

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

Тогда: 

dp[n][m]

Это ответ для всей строки s и всей строки t.

dp[n][m] = длина LCS двух полных строк

Пример руками

Пусть: 

s = "abc"
t = "ac"

Ответ должен быть: 

2

Потому что общая подпоследовательность — "ac".

Состояние Смысл
dp[1][1] LCS("a", "a") = 1
dp[2][1] LCS("ab", "a") = 1
dp[3][2] LCS("abc", "ac") = 2

Рекурсивный метод

Эту задачу можно сначала понять через рекурсию.

Пусть: 

solve(i, j)

Это длина LCS для первых i символов строки s и первых j символов строки t.

Если i == 0 или j == 0, ответ 0. 

if (i == 0 || j == 0) {
    return 0;
}

Рекурсивный переход

Если последние символы равны: 

solve(i, j) = solve(i - 1, j - 1) + 1

Если последние символы разные: 

solve(i, j) = max(solve(i - 1, j), solve(i, j - 1))

Рекурсия + мемоизация

int solve(int i, int j) {
    if (i == 0 || j == 0) {
        return 0;
    }

    if (dp[i][j] != -1) {
        return dp[i][j];
    }

    if (s[i - 1] == t[j - 1]) {
        dp[i][j] = solve(i - 1, j - 1) + 1;
    } else {
        dp[i][j] = max(solve(i - 1, j), solve(i, j - 1));
    }

    return dp[i][j];
}

Полная рекурсивная реализация

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

string s, t;
int dp[N][N];

int solve(int i, int j) {
    if (i == 0 || j == 0) {
        return 0;
    }

    if (dp[i][j] != -1) {
        return dp[i][j];
    }

    if (s[i - 1] == t[j - 1]) {
        dp[i][j] = solve(i - 1, j - 1) + 1;
    } else {
        dp[i][j] = max(solve(i - 1, j), solve(i, j - 1));
    }

    return dp[i][j];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s >> t;

    memset(dp, -1, sizeof(dp));

    cout << solve(s.size(), t.size());

    return 0;
}

Рекурсия → итеративный DP

Рекурсия Итеративный DP
solve(i, j) dp[i][j]
solve(i - 1, j - 1) dp[i - 1][j - 1]
solve(i - 1, j) dp[i - 1][j]
solve(i, j - 1) dp[i][j - 1]
base case нулевая строка и нулевой столбец

Восстановление самой LCS

Иногда нужно вывести не только длину, но и саму подпоследовательность.

После заполнения dp идем назад из состояния: 

i = n;
j = m;

Если символы равны, значит этот символ входит в ответ: 

if (s[i - 1] == t[j - 1]) {
    answer.push_back(s[i - 1]);
    i--;
    j--;
}

Если символы разные

Если символы разные, идем туда, где значение dp больше. 

if (dp[i - 1][j] > dp[i][j - 1]) {
    i--;
} else {
    j--;
}

В конце ответ будет собран с конца, поэтому надо сделать: 

reverse(answer.begin(), answer.end());

Код восстановления LCS

string answer;

int i = n;
int j = m;

while (i > 0 && j > 0) {
    if (s[i - 1] == t[j - 1]) {
        answer.push_back(s[i - 1]);
        i--;
        j--;
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
        i--;
    } else {
        j--;
    }
}

reverse(answer.begin(), answer.end());

Полная реализация с восстановлением

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

string s, t;
int dp[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s >> t;

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

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

    string answer;

    int i = n;
    int j = m;

    while (i > 0 && j > 0) {
        if (s[i - 1] == t[j - 1]) {
            answer.push_back(s[i - 1]);
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    reverse(answer.begin(), answer.end());

    cout << dp[n][m] << '\n';
    cout << answer;

    return 0;
}

Пример с восстановлением

Input

abac
cab

Output

2
ab

Возможен и другой правильный ответ, если LCS несколько.

Оптимизация памяти

Если нужна только длина LCS, можно хранить не весь массив dp[n][m], а только две строки. 

vector<int> prev(m + 1);
vector<int> cur(m + 1);

Потому что dp[i][j] зависит только от:

  • dp[i - 1][j - 1]
  • dp[i - 1][j]
  • dp[i][j - 1]

Реализация с памятью O(m)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s, t;
    cin >> s >> t;

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

    vector<int> prev(m + 1, 0);
    vector<int> cur(m + 1, 0);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                cur[j] = prev[j - 1] + 1;
            } else {
                cur[j] = max(prev[j], cur[j - 1]);
            }
        }

        prev = cur;
    }

    cout << prev[m];

    return 0;
}
Если нужно восстановить саму подпоследовательность, обычно удобнее хранить полный dp[n][m].

LCS и LIS

Задача Что дано Что ищем
LIS один массив самую длинную возрастающую подпоследовательность
LCS две строки или два массива самую длинную общую подпоследовательность

Типичные ошибки

  • Путать подпоследовательность и подстроку
  • Забыть, что можно пропускать символы
  • Писать s[i] вместо s[i - 1]
  • Писать t[j] вместо t[j - 1]
  • Неправильно заполнить нулевую строку и нулевой столбец
  • При восстановлении забыть сделать reverse
  • Думать, что LCS всегда единственная

Асимптотика

Метод Время Память
Рекурсия + мемоизация O(nm) O(nm)
Итеративный DP O(nm) O(nm)
Оптимизация памяти O(nm) O(m)
Здесь n — длина первой строки, m — длина второй строки.

Как думать на задачах LCS?

1. Есть две строки или два массива
2. Нужно найти общую подпоследовательность
3. Состояние dp[i][j]
4. Если символы равны — берем их
5. Если разные — берем максимум из двух вариантов
6. Ответ лежит в dp[n][m]

Короткий шаблон

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

cout << dp[n][m];