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

Задача нахождения наибольшей общей подпоследовательности (англ. 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]s1[i] \lt \gt s2[j][/math] (соответствующие элементы последовательностей не равны).Очевидно, что сложность алгоритма составит [math]O(n^2)[/math].

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

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

Построение подпоследовательности

Для каждой пары элементов будем хранить не только длину НОП соответствующих префиксов, но и номера последних элементов, участвующих в этой НОП.Таким образом, посчитав ответ, мы сможем восстановить всю наибольшую общую подпоследовательность.

Пример реализации на Java

     public int[] lcs(int[] s1, int[] s2) {
         int[][] a = new int[s1.length][s2.length];
         int[][] last_1 = new int[s1.length][s2.length];
         int[][] last_2 = new int[s1.length][s2.length];
         //Подсчет значений
         for (int i = 0; i < s1.length; i++)
             for (int j = 0; j < s2.length; j++) {
                 if (s1[i] == s2[j])
                     if ((i == 0) || (j == 0)) {
                         a[i][j] = 1;
                         last_1[i][j] = i;
                         last_2[i][j] = j;
                     } else {
                         a[i][j] = a[i - 1][j - 1] + 1;
                         last_1[i][j] = i;
                         last_2[i][j] = j;
                     }
                 else {
                     if ((i > 0) && (a[i - 1][j] > a[i][j])) {
                         a[i][j] = a[i - 1][j];
                         last_1[i][j] = last_1[i - 1][j];
                         last_2[i][j] = last_2[i - 1][j];
                     }
                     if ((j > 0) && (a[i][j - 1] > a[i][j])) {
                         a[i][j] = a[i][j - 1];
                         last_1[i][j] = last_1[i][j - 1];
                         last_2[i][j] = last_2[i][j - 1];
                     }
                 }
             }
             
         //Восстановление последовательности
         int l = a[s1.length - 1][s2.length - 1];
         int[] ans = new int[l];
         int ti = s1.length - 1;
         int tj = s2.length - 1;
         while (l > 0){
             ans[l - 1] = s1[last_1[ti][tj]];
             int nti = last_1[ti][tj] - 1;
             int ntj = last_2[ti][tj] - 1;
             ti = nti;
             tj = ntj;
             l--;
         }
         return ans;
     }