Изменения

Последовательность <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_m 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_m x_n \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, \dots, y_n 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>. Получается следующее рекуррентное соотношение:

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

В Для восстановления ответа заведем массив <tex> scsprev[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[i - 1][j] > scs[i][j - 1] \\ 3, зная длину SCS& 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[]'''): n = x.size m = y.size '' ''<font color="green">// аналог void инициализация массивов динамики </font>'' m scs = '''int'''[][] pref = x.size'''int'''[][] '' n ''<font color= y.size"green">// случай равенства одного из индексов 0 </font>'' '''for''' i = 1 0 '''to''' mn

'''for''' j = 0 '''to''' nm

'' '''for''' i = 1 '''to''' mn '''for''' j = 1 '''to''' nm ''<font color="green">// случай равенства элементов </font>''

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(mn: '''int''', nm: '''int'''): ''<font color="green">// вывод SCS</font>'' i = mn j = nm

'''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>XS</tex> являетcя подпоследовательностью суперпоследовательностью <tex> S X </tex>, то можно представить <tex>S</tex> так:

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