Изменения

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

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

Последовательность <tex> Z z </tex> является '''общей подпоследовательностью''' (common subsequence) последовательностей <tex> X x </tex> и <tex> Y y </tex>, если <tex> Z z </tex> является подпоследовательностью как <tex> X x </tex>, так и <tex> Y y </tex>.

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

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

alcs[i][j] =

alcs[i - 1][j - 1] + 1, & x[i] = y[j] \\ max(alcs[i][j - 1], alcs[i - 1][j]), & x[i] \neq y[j]

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

<tex> X x </tex>, <tex> Y y </tex> — данные последовательности; <tex> alcs[i][j] </tex> — НОП для префикса длины <tex> i </tex> последовательности <tex> X x </tex> и префикса длины <tex> j </tex> последовательности <tex> Y y </tex>; <tex> bprev[i][j] </tex> — пара индексов элемента таблицы, соответствующего оптимальному решению вспомогательной задачи, выбранной при вычислении <tex> alcs[i][j] </tex>.

LCS(Xx, Yy) m = length(Xx) n = length(Yy)

alcs[i][0] = 0

alcs[0][j] = 0

if x[i] == y[i] alcs[i][j] = alcs[i - 1][j - 1] + 1 bprev[i][j] = pair(i - 1, j - 1)

alcs[i][j] = alcs[i - 1][j] bprev[i][j] = pair(i - 1, j)

alcs[i][j] = alcs[i][j - 1] bprev[i][j] = pair(i, j - 1)

// вывод НОП, вызывается как PrintLCS(prev, x, m, n) PrintLCS(bprev, Xx, i, j) if i == 0 or j == 0 // пришли к началу НОП

if bprev[i][j] == pair(i - 1, j - 1) // если пришли в alcs[i][j] из alcs[i - 1][j - 1], то Xx[i] = Y= y[j], надо вывести этот элемент PrintLCS(bprev, Xx, i - 1, j - 1) print Xx[i]

if bprev[i][j] == pair(i - 1, j) PrintLCS(bprev, Xx, i - 1, j)

PrintLCS(bprev, Xx, i, j - 1)

Заметим, что для вычисления <tex> alcs[i][j] </tex> нужны только <tex> i </tex>-ая и <tex> (i-1) </tex>-ая строчки матрицы <tex> a lcs </tex>. Тогда можно использовать лишь <tex> 2 \cdot min(m, n) </tex> элементов таблицы:

LCS2(Xx, Yy) if length(Xx) < length(Yy) // в таблице будет length(Yy) столбцов, и если length(Xx) меньше, выгоднее поменять местами X x и Yy swap(Xx, Yy) m = length(Xx) n = length(Yy)

alcs[0][j] = 0 alcs[1][j] = 0

alcs[1][0] = 0

alcs[0][j] = alcs[1][j] // элемент, который был в a[1][j], теперь в предыдущей строчке if x[i] == y[i] alcs[1][j] = alcs[0][j - 1] + 1

if alcs[0][j] >= alcs[1][j - 1] alcs[1][j] = alcs[0][j]

alcs[1][j] = alcs[1][j - 1] // ответ — alcs[1][n]

LCS3(Xx, Yy) if length(Xx) < length(Yy) // в таблице будет length(Yy) столбцов, и если length(Xx) меньше, выгоднее поменять местами X x и Yy swap(Xx, Yy) m = length(Xx) n = length(Yy)

alcs[j] = 0 d = 0 // d — дополнительная переменная, в ней хранится alcs[i - 1][j - 1] // в alcs[j], alcs[j + 1], …, alcs[n] хранятся alcs[i - 1][j], alcs[i - 1][j + 1], …, alcs[i - 1][n] // в alcs[0], alcs[1], …, alcs[j - 1] хранятся alcs[i][0], alcs[i][1], …, alcs[i][j - 1]

tmp = alcs[j] if x[i] == y[i] alcs[j] = d + 1

if alcs[j] >= alcs[j - 1] alcs[j] = alcs[j] // в alcs[j] и так хранится alcs[i - 1][j]

alcs[j] = alcs[j - 1]

// ответ — alcs[n]