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

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

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

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

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

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

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

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

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

${\displaystyle 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.}$

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

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

См. также

• Наибольшая общая подстрока

Ссылки

• (рус.) . algolist.ru. Дата обращения: 15 августа 2013. 24 августа 2013 года.

• (рус.) . coders.ask-ru.net.