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

Задача нахождения наибольшей общей подпоследовательности (англ. longest common subsequence, LCS) — задача поиска последовательности, которая является подпоследовательностью нескольких последовательностей (обычно двух). Часто задача определяется как поиск всех наибольших подпоследовательностей. Это классическая задача информатики, которая имеет приложения, в частности, в задаче сравнения текстовых файлов (утилита diff), а также в биоинформатике.

Подпоследовательность можно получить из некоторой конечной последовательности, если удалить из последней некоторое множество её элементов (возможно пустое). Например, BCDB является подпоследовательностью последовательности ABCDBAB. Будем говорить, что последовательность Z является общей подпоследовательностью последовательностей X и Y, если Z является подпоследовательностью как X, так и Y. Требуется для двух последовательностей X и Y найти общую подпоследовательность наибольшей длины. Заметим, что НОП может быть несколько.

Обратите внимание! Подпоследовательность отличается от подстроки. Например, если есть исходная последовательность «ABCDEF», то «ACE» будет подпоследовательностью, но не подстрокой, а «ABC» будет как подпоследовательностью, так и подстрокой.

Решение задачи

Сравним два метода решения: полный перебор и динамическое программирование.

Полный перебор

Существуют разные подходы при решении данной задачи при полном переборе — можно перебирать варианты подпоследовательности, варианты вычеркивания из данных последовательностей и т. д. Однако в любом случае, время работы программы будет полиномом от длин строк.

Метод динамического программирования

		A	B	C	D
	0	0	0	0	0
D	0	← 0	← 0	← 0	↖ 1
C	0	← 0	← 0	↖ 1	← 1
D	0	← 0	← 0	↑ 1	↖ 2
A	0	↖ 1	← 1	← 1	↑ 2

Вначале найдём длину наибольшей подпоследовательности. Допустим, мы ищем решение для случая (n₁, n₂), где n₁, n₂ — длины первой и второй строк. Пусть уже существуют решения для всех подзадач (m₁, m₂), меньших заданной. Тогда задача (n₁, n₂) сводится к меньшим подзадачам следующим образом:

$f(n_{1},n_{2})=\left\{{\begin{array}{ll}0,&n_{1}=0\lor 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.$

Теперь вернемся к задаче построения подпоследовательности. Для этого в существующий алгоритм добавим запоминание для каждой задачи той подзадачи, через которую она решается. Следующим действием, начиная с последнего элемента, поднимаемся к началу по направлениям, заданным первым алгоритмом, и записываем символы в каждой позиции. Это и будет ответом в данной задаче.

Время работы алгоритма будет $\mathrm {O} \,(n_{1}\cdot n_{2})$.

См. также

• Алгоритмы на строках
• Наибольшая общая подстрока

Ссылки

• Нахождение наибольшей общей подпоследовательности (рус.). algolist.ru. Дата обращения: 15 августа 2013.

• Алгоритм поиска длины наибольшей общей подпоследовательности (рус.). coders.ask-ru.net.