Наибольшая общая подпоследовательность из двух последовательностей
Мы имеем две последовательности $A=(a_1, a_2, \dotsc, a_n)$ и $B=(b_1, b_2, \dotsc, b_m)$, их общая подпоследовательность длиной $p$ — это набор $p$ индексов
Такая задача может применяться, например: — в сопоставлении данных — утилита diff, операция слияния в разных системах управления версиями; — в биоинформатике — поиск сходств в генах разных видов; — в проверке орфографии.
- Входные данные: Первая строка: количество элементов первой подпоследовательности $n$. Вторая строка: $a_1, a_2, \dotsc, a_n$. Третья строка: количество элементов второй подпоследовательности $m$. Четвёртая строка: $b_1, b_2, \dotsc, b_m$.
- Выходные данные: $p$.
- Ограничения: $1 \le n, m \le 100$; $-10^9 \le a_i,b_i \le 10^9$ для всех $i$.
Пример 1
Ввод | Вывод |
---|---|
3 2 7 5 2 2 5 | 2 |
- Общая подпоследовательность длиной 2 — это $(2,5)$.
Пример 2
Ввод | Вывод |
---|---|
1 7 4 1 2 3 4 | 0 |
- У двух последовательностей нет общих элементов.
Пример 3
Ввод | Вывод |
---|---|
4 2 7 8 3 4 5 2 8 7 | 2 |
- Одна общая подпоследовательность — $(2,7)$. Ещё одна — $(2,8)$.
Решение
Рассмотрим наибольшую общую подпоследовательность $C=(c_1,\dotsc,c_p)$, определённую индексами $1 \le i_1 < i_2 < \dotsb < i_p \le n$ и $1 \le j_1 < j_2 < \dotsb < j_p \le m$ (так, для каждого $1 \le q \le p$, $a_{i_q}=b_{j_q}=c_q$): — Последние символы $A$ и $B$ приводятся в $C$. В этом случае $i_p=n$ и $j_p=m$. Тогда $(c_1,\dotsc, c_{p-1})$ — это наибольшая общая подпоследовательность от $(a_1, \dotsc, a_{n-1})$ и $(b_1, \dotsc, b_{m-1})$. — Как минимум один из последних символов $A$ и $B$ не приводится в $C$. В этом случае или $i_p<n$, или $j_p<m$. Тогда $(c_1,\dotsc, c_{p-1})$ находится полностью в $(a_1, \dotsc, a_{n-1})$ или $(b_1, \dotsc, b_{m-1})$.
Таким образом, мы сводим задачу с изначальными строками $A$ и $B$ до такой же задачи с их префиксами. Пусть $LCS(i,j)$ — длина наибольшей общей подпоследовательности $A[1\dotsc i]$ и $B[1 \dotsc j]$. Выходит, что эта функция удовлетворяет следующее рекуррентное соотношение:
$$ LCS(0,j)=LCS(i,0)=0 , . $$
Полученный алгоритм приведён ниже. Его время выполнения составляет $O(nm)$.
LCS(A[1…n],B[1…m]):
table = 2d array of size (n+1)×(m+1)
table[i][0] = 0 and table[0][j] = 0 for all i,j
for i from 1 to n:
for j from 1 to m:
table[i][j] = table[i−1][j]
table[i][j] = max(table[i][j], table[i][j−1])
if A[i]=B[j]:
table[i][j] = max(table[i][j], table[i−1][j−1]+1)
return table[n][m]
💡 Остановитесь и подумайте:
Получится ли у вас свести задачу «Наибольшая общая подпоследовательность» до задачи «Редакционное расстояние»?
Подсказка: Наибольшая общая подпоследовательность $A=(7,2,9,3,1,5,9,4)$ и $B=(2,8,1,3,9,7)$ получается путём удаления определённых символов из $A$ и $B$.
Так задача «Наибольшая общая подпоследовательность» — всего лишь задача «Редакционное расстояние», в которой запрещены операции «замены».
Наибольшая общая подпоследовательность из трёх последовательностей
Имея три последовательности: $A=(a_1, a_2, \dotsc, a_n)$, $B=(b_1, b_2, \dotsc, b_m)$ и $C=(c_1, c_2, \dotsc, c_l)$ — нужно найти длину наибольшей общей подпоследовательности для них, то есть наибольшее неотрицательное целое число $p$, при котором существуют индексы
при котором
- Входные данные: Первая строка: $n$. Вторая строка: $a_1, a_2, \dotsc, a_n$. Третья строка: $m$. Четвёртая строка: $b_1, b_2, \dotsc, b_m$. Пятая строка: $l$. Шестая строка: $c_1, c_2, \dotsc, c_l$.
- Выходные данные: $p$.
- Ограничения: $1 \le n,m,l \le 100$; $-10^9 \le a_i,b_i,c_i \le 10^9$.
Пример 1
Ввод | Вывод |
---|---|
3 1 2 3 3 2 1 3 3 1 3 5 | 2 |
- Общая подпоследовательность длиной 2 — это $(1,3)$.
Пример 2
Ввод | Вывод |
---|---|
5 8 3 2 1 7 7 8 2 1 3 8 10 7 6 6 8 3 1 4 7 | 3 |
- В этом случае одна общая подпоследовательность длиной 3 — это $(8, 3, 7)$. Ещё одна — $(8, 1, 7)$.
Решение
Пусть $LCS(i,j,k)$ — это максимальная длина общей подпоследовательности от $A[1\dotsc i]$, $B[1 \dotsc j]$ и $C[1 \dotsc k]$.
Тогда
Базовый случай: $$ LCS(0,j,k)=LCS(i,0,k)=LCS(i,j,0)=0 . $$
Время выполнения соответствующего алгоритма составляет $O(nmk)$.