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

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

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

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

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

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