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

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

Определения

Определение:

Последовательность [math] Z = \left \langle z_1, z_2, ..., z_k \right \rangle [/math] является подпоследовательностью (subsequence) последовательности [math] X = \left \langle x_1, x_2, ..., x_m \right \rangle [/math], если существует строго возрастающая последовательность [math] \left \langle i_1, i_2, ..., i_k \right \rangle [/math] индексов [math] X [/math] таких, что для всех [math] j = 1, 2, ..., k [/math] выполняется соотношение [math] x_{i_j} = z_j [/math].

Другими словами, подпоследовательность данной последовательности — это последовательность, из которой удалили ноль или больше элементов. Например, [math] Z = \left \langle B, C, D, B \right \rangle [/math] является подпоследовательностью последовательности [math] X = \left \langle A, B, C, B, D, A, B \right \rangle [/math], а соответствующая последовательность индексов имеет вид [math] \left \langle 2, 3, 5, 7 \right \rangle [/math].

Определение:

Последовательность [math] Z [/math] является общей подпоследовательностью (common subsequence) последовательностей [math] X [/math] и [math] Y [/math], если [math] Z [/math] является подпоследовательностью как [math] X [/math], так и [math] Y [/math].

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

Даны две последовательности: [math] X = \left \langle x_1, x_2, ..., x_m \right \rangle [/math] и [math] Y = \left \langle y_1, y_2, ..., y_n \right \rangle [/math]. Требуется найти общую подпоследовательность [math] X [/math] и [math] Y [/math] максимальной длины. Заметим, что таких подпоследовательностей может быть несколько.

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

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

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

Решение

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

[math] a[i][j] = \begin{cases} a[i - 1][j - 1] + 1, & x[i] = y[j] \\ max(a[i][j - 1], a[i - 1][j]), & x[i] \neq y[j] \end{cases} [/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];
     //Подсчет значений
     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;
                 } else {
                     a[i][j] = a[i - 1][j - 1] + 1;
                 }
             else {
                 if ((i > 0) && (a[i - 1][j] > a[i][j])) {
                     a[i][j] = a[i - 1][j];
                 }
                 if ((j > 0) && (a[i][j - 1] > a[i][j])) {
                     a[i][j] = a[i][j - 1];
                 }
             }
         }
     return a[s1.length - 1][s2.length - 1];
   }