НОП

Материал из Algocode wiki
Версия от 13:50, 22 октября 2019; Глеб (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Даны две последовательности $a_1,\ldots,a_n$ и $b_1,\ldots,b_m$. Требуется найти длину их наибольшей общей подпоследовательности (НОП), то есть длину наибольшей таких последовательностей $i_1<\ldots<i_k$ и $j_1<\ldots<j_k$, что $a[i_1]=b[j_1],\ldots,a[i_k]=b[j_k]$.

Решим эту задачу с помощью динамического программирования, где $dp[i][j]$ будет обозначать длину НОП, если мы рассмотрели префиксы последовательностей длины $i$ и $j$.

Тогда заметим, что есть две ситуации, когда мы считаем $dp[i][j]$:

  • $a_i \neq b_j$, тогда хотя бы один из этиз символов не содержится в НОП, иначе она заканчивается на два разных символа. В этом случае $dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])$
  • $a_i = b_j$, тогда несложно доказать, что точно есть максимальная НОП, в которую входят ОБА этих символа, а значит $dp[i][j] = 1 + dp[i - 1][j - 1]$.

А на пустых префиксах ответ 0.

1 for (int i = 1; i <= n; i++) {
2     for (int j = 1; j <= m; j++) {
3         dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
4         if (a[i - 1] == b[j - 1]) {
5             dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
6         }
7     }
8 }

Ответом является максимальное число в массиве $dp$. Решение работает за $O(nm)$.

Ответ при это восстанавливается классическим способом - с конца. Нам все еще нужно просто в каждой ячейке смотреть - если символы в ней равны, то нужно уменьшить $i$ и $j$, иначе только один из них - так, чтобы НОП был максимален.



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin