Русская Википедия:Наибольшая общая подпоследовательность
Задача нахождения наибольшей общей подпоследовательности (Шаблон:Lang-en, LCS) — задача поиска последовательности, которая является подпоследовательностью нескольких последовательностей (обычно двух). Часто задача определяется как поиск всех наибольших подпоследовательностей. Это классическая задача информатики, которая имеет приложения, в частности, в задаче сравнения текстовых файлов (утилита diff), а также в биоинформатике.
Подпоследовательность можно получить из некоторой конечной последовательности, если удалить из последней некоторое множество её элементов (возможно пустое). Например, BCDB является подпоследовательностью последовательности ABCDBAB. Будем говорить, что последовательность Z является общей подпоследовательностью последовательностей X и Y, если Z является подпоследовательностью как X, так и Y. Требуется для двух последовательностей X и Y найти общую подпоследовательность наибольшей длины. Заметим, что НОП может быть несколько.
Обратите внимание! Подпоследовательность отличается от подстроки. Например, если есть исходная последовательность "ABCDEF", то "ACE" будет подпоследовательностью, но не подстрокой, а "ABC" будет как подпоследовательностью, так и подстрокой.
Решение задачи
Сравним два метода решения: полный перебор и динамическое программирование.
Полный перебор
Существуют разные подходы при решении данной задачи при полном переборе — можно перебирать варианты подпоследовательности, варианты вычеркивания из данных последовательностей и т. д. Однако в любом случае, время работы программы будет экспонентой от длины строки.
Метод динамического программирования
| A | B | C | B | ||
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | |
| D | 0 | ← 0 | ← 0 | ← 0 | ← 0 |
| C | 0 | ← 0 | ← 0 | ↖ 1 | ← 1 |
| B | 0 | ← 0 | ↖ 1 | ← 1 | ↖ 2 |
| A | 0 | ↖ 1 | ← 1 | ← 1 | ↑ 2 |
Вначале найдём длину наибольшей подпоследовательности. Допустим, мы ищем решение для случая (n1, n2), где n1, n2 — длины первой и второй строк. Пусть уже существуют решения для всех подзадач (m1, m2), меньших заданной. Тогда задача (n1, n2) сводится к меньшим подзадачам следующим образом:
<math> f(n_1, n_2) = \left \{ \begin{array}{ll}
0, & n_1 = 0 \or n_2 = 0 \\
f(n_1 - 1, n_2 - 1) + 1, & s_1[n_1] = s_2[n_2] \\
max(f(n_1 - 1, n_2), f(n_1, n_2 - 1)), & s_1[n_1] \neq s_2[n_2]
\end{array}
\right.
</math>
Теперь вернемся к задаче построения подпоследовательности. Для этого в существующий алгоритм добавим запоминание для каждой задачи той подзадачи, через которую она решается. Следующим действием, начиная с последнего элемента, поднимаемся к началу по направлениям, заданным первым алгоритмом, и записываем символы в каждой позиции. Это и будет ответом в данной задаче.
Время работы алгоритма будет <math>\mathrm{O}\,(n_1 \cdot n_2)</math>.
См. также
Ссылки
Шаблон:Нет ссылок Шаблон:Перевести
