Задача о наименьшей суперпоследовательности

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

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

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

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

Задача:

Пусть имеются последовательности [math] X = \left \langle x_1, x_2, \dots, x_m \right \rangle [/math] и [math] Y = \left \langle y_1, y_2, \dots, y_n \right \rangle [/math]. Необходимо найти [math]SCS(X,Y)[/math]

Наивное решение

Заметим, что если приписать к одной из данной последовательность другую, то полученная последовательность будет их суперпоследовательностью с длиной [math] n + m [/math]. Запомним все элементы обеих последовательностей и из них построим все возможные последовательности. Тогда искомая [math]SCS[/math] гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.

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

Решение

Обозначим за [math] scs[i][j] [/math] SCS префиксов данных последовательностей [math] x[1 \dots n] [/math] и [math] y[1 \dots m] [/math], заканчивающихся в элементах с номерами [math] i [/math] и [math] j [/math] соответственно. Наименьшая общая суперпоследовательность [math] x[1 \dots i] [/math] и [math] y[1 \dots j] [/math] должна содержать каждый символ обеих последовательностей, поэтому если [math] j = 0 [/math], то [math] SCS [/math] это просто последовательность [math] x[1 \dots i] [/math]. Аналогичен случай, когда [math] i = 0 [/math]. Если [math] i \gt 0 [/math] и [math] j \gt 0 [/math], то возможны два случая. Если [math] x[i] \neq y[j] [/math], то SCS должна включать оба этих элемента. Значит нужно выбрать оптимальный из ответов для префиксов, включающих один элемент и не включающих второй, и выбрать из них минимальный. Если же [math] x[i] = y[j] [/math], то SCS для последовательностей [math] x[1 \dots i] [/math] и [math] y[1 \dots j] [/math] должна заканчиваться этим элементом, так как он общий для них. Получается следующее рекуррентное соотношение:

[math] scs[i][j] = \begin{cases} i, & j = 0 \\ j, & i = 0 \\ 1 + scs[i - 1][j - 1], & x[i] = y[j] \\ 1 + min(scs[i][j - 1],\ scs[i - 1][j]), & x[i] \neq y[j] \end{cases} [/math]

Очевидно, что сложность алгоритма составит [math] O(mn) [/math], где [math] m [/math] и [math] n [/math] — длины последовательностей.

Восстановление ответа

В [math] scs[i][j] [/math] помимо длины последовательности хранятся и символ, добавленный последним. Таким образом, зная длину SCS, можно восстановить и саму последовательность.

Псевдокод

x, y — данные последовательности; scs[i][j] — SCS для префикса длины i последовательности x и префикса длины j последовательности y; prev[i][j] — пара индексов элемента таблицы, соответствующего оптимальному решению вспомогательной задачи, выбранной при вычислении scs[i][j].