Задача о наибольшей общей подпоследовательности

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

Постановка задачи

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

Наивная идея решения

Переберем все различные подпоследовательности обеих строк и сравним их. Мы гарантированно найдем искомую НОП, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.

Динамическое программирование

Решение

Обозначим как [math]a_{i, j}[/math] НОП префиксов данных последовательностей длины [math]i[/math] и [math]j[/math] соответственно.Получаем следующее рекуррентное соотношение:

• [math]a_{i, j} = a_{i - 1, j - 1} + 1[/math], если [math]s[i] = s[j][/math] (соответствующие элементы последовательностей равны)
• [math]a_{i, j} = max(a_{i, j - 1}, a_{i - 1, j})[/math], если [math]s[i] \lt \gt s[j][/math] (соответствующие элементы последовательностей не равны)

Доказательство оптимальности

Предположим, что некоторое значение [math]a_{i, j}[/math] посчитано неверно. Однако, в случае равенства соответствующих символов,