Изменения

Последовательность <tex> Z = \left \langle z_1, z_2, \dots, z_k \right \rangle </tex> является '''суперпоследовательностью''' (англ. ''supersequence'') последовательности <tex> X = \left \langle x_1, x_2, \dots, x_n \right \rangle </tex>, если <tex>X</tex> — подпоследовательность <tex>Z</tex> , то есть существует ''строго возрастающая'' последовательность <tex> \left \langle i_1, i_2, \dots, i_m i_n \right \rangle </tex> индексов <tex> Z </tex> таких, что для всех <tex> j = 1, 2, \dots, m n </tex> выполняется соотношение <tex> z_{i_j} = x_j </tex>, при этом <tex> k \geqslant n </tex>.

Пусть имеются последовательности <tex> X = \left \langle x_1, x_2, \dots, x_n \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, \dots, y_m \right \rangle </tex>. Необходимо найти <tex>SCS(X,Y)</tex>, где <tex>SCS(X, Y)</tex> — длина наименьшей общей суперпоследовательности последовательностей <tex> X </tex> и <tex> Y </tex>

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

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

Для восстановления ответа заведем массив <tex> prev[0 \dots n][0\dots m] </tex>, где <tex>prev[i][j]</tex> будет означать индексы в массиве равняться: <tex>prev[i][j] =\begin{cases} 1, & x[i] = y[j] \\ 2, & x[i] \neq y[j], scs</tex[i - 1][j] >scs[i][j - 1] \\ 3, при которых достигалось наименьшее значение <tex>sc& x[i] \neq y[j], scs[i - 1][j] \leqslant scs[i][j- 1]\\ \end{cases}</tex> По этим данным можно узнать, какой символ был добавлен в наименьшую общую суперпоследовательность.

<tex> x, y </tex> — данные последовательности; <tex>scs[i][j] </tex> — <tex>SCS </tex> для префикса длины <tex>i </tex> последовательности <tex>x </tex> и префикса длины <tex>j </tex> последовательности <tex>y</tex>; prev[i][j] — пара индексов элемента таблицы, которые предшествовали <tex>scsprev[i][j]</tex>— массив для восстановления ответа.

''<font color="green">// Подсчет динамики </font>'' '''fun''' SCS(x: '''int[]''', y: '''int[]'''): ''<font color="green">// аналог void </font>''

'' ''<font color="green">// инициализация массивов динамики </font>'' scs = '''int'''[][] pref = '''int'''[][] '' ''<font color="green">// случай равенства одного из индексов 0 </font>'' '''for''' i = 1 0 '''to''' n

prev[i][j] = pair(i - 1, j - 1)

''<font color="green">// случай неравенства элементов </font>'' '''if''' scs[i - 1][j] <> scs[i][j - 1] scs[i][j] = lcs1 + scs[i][j - 1] prev[i][j] = 2 '''else'''

prev[i][j] = pair(i - 1, j)3  '''else'<font color="green">// вывод SCS </font>'' scs[i][j] = 1 + scs[i][j - 1] prev[i][j] = pair(i, j - 1) '''fun''' printLCSprintSCS(n: '''int''', m: '''int'''): ''<font color="green">// вывод SCS</font>''

'''if''' prev[i][j] == pair(i - 1, j - 1)

'''if''' prev[i][j] == pair2 ans.append(i y[j]) j - = 1, j) '''else'''

'''else' '' ans.append(y[j]) j -= 1 '''while''' i > 0 ''<font color="green">// добавляем оставшиеся символы первой последовательности </font>'' '''while''' i > 0

ans.append(y[j]) ''<font color="green">// добавляем оставшиеся символы второй последовательности </font>''

<tex>|LCS(X, Y)| + |SCS(X, Y)| = n + m</tex>, где <tex>|LCS(X, Y)|</tex> - — длина [[Задача о наибольшей общей подпоследовательности| наибольшей общей подпоследовательности]], <tex>|SCS(X, Y)|</tex> - — длина наименьшей общей суперпоследовательности, <tex>n</tex> и <tex>m</tex> - — длины последовательностей <tex> X </tex> и <tex> Y </tex> соответсвенносоответственно.

|proof= Пусть <tex> X = \left \langle x_1, x_2, \dots, x_n \right \rangle </tex>, <tex> Y = \left \langle y_1, y_2, \dots, x_m \right \rangle </tex>. Обозначим за <tex> S </tex> их <tex>SCS </tex> и будем ее строить. Так как <tex>S</tex> являетcя суперпоследовательностью <tex> X </tex>, то можно представить <tex>S</tex> так:

Мы должны поставить на место некоторых пропусков поставить элементы <tex>Y</tex>, так чтобы суммарная длина <tex> S </tex> была минимальна, и <tex> S </tex> был являлась суперпоследовательностью <tex>XY</tex>. Рассмотрим любую общую подпоследовательность <tex>X</tex> и <tex>Y</tex>.Заметим, что она уже находятся в <tex>S</tex>, а значит все её элементы не нужно добавлять. Поэтому мы добавим не меньше , чем <tex> m - |LCS(X, Y)| элементов </tex>. Длину <tex> SCS(X, Y) </tex> нужно минимизировать, значит имеет место равенство: