Изменения

Последовательность <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> Z </tex> является '''общей суперпоследовательностью''' (англ. ''common supersequence'') последовательностей <tex> X </tex> и <tex> Y </tex>, если <tex> X Z </tex> и является суперпоследовательностью как для <tex> Y X </tex> являются подпоследовательностями , так для и <tex> Z Y </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] </tex> SCS длину наименьшей общей суперпоследовательности для префиксов данных последовательностей <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) '''intfun''' printLCSprintSCS(mn: '''int''', nm: '''int'''): ''<font color i ="green">// вывод SCS, вызывается как printLCS(m, n)</font>'' '''if''' i == 0 '''or''' j =m ans = 0 [] ''<font color="green">// пришли к началу LCSмассив ответа </font>'' '''return' '' '''ifwhile''' prev[i][j] == pair(i - 1, j - 1) ''<font color="green">// если пришли в lcs[i][j] из lcs[i - 1][j - 1], то x[i] == y[j], надо вывести этот элемент</font>0 '' printLCS(i - 1, j - 1) print x[i] '''elseand'''j > 0 '''if''' prev[i][j] == pair1 ans.append(x[i - 1, j]) printLCS(i - = 1, j)-= 1

printLCS'''if''' prev[i][j] == 2 ans.append(y[j]) j -= 1 '''else''' ans.append(x[i]) i -= 1 '' ''<font color="green">// добавляем оставшиеся символы первой последовательности </font>'' '''while''' i > 0 ans.append(x[i]) i, -= 1 ''<font color="green">// добавляем оставшиеся символы второй последовательности </font>'' '''while''' j > 0 ans.append(y[j]) j - = 1 '' '''reverse'''(ans) ''<font color="green">// разворачиваем последовательность, так как шли с конца </font>'' '''return''' ans ==Связь с наибольшей общей подпоследовательностью=={{Теорема|statement=<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> S = \dots x_1 \dots x_2 \dots x_i \dots x_n \dots </tex>Мы должны на место некоторых пропусков поставить элементы <tex>Y</tex>, так чтобы суммарная длина <tex> S </tex> была минимальна, и <tex> S </tex> являлась суперпоследовательностью <tex>Y</tex>. Рассмотрим любую общую подпоследовательность <tex>X</tex> и <tex>Y</tex>. Заметим, что она уже находятся в <tex>S</tex>, а значит все её элементы не нужно добавлять. Поэтому мы добавим не меньше, чем <tex> m - |LCS(X, Y)| элементов </tex>. Длину <tex> SCS(X, Y) </tex> нужно минимизировать, значит имеет место равенство:<tex>|SCS(X,Y)| = n + (m - |LCS(X, Y)|)</tex>. Поэтому: <tex>|LCS(X, Y)| + |SCS(X, Y)| = n + m</tex> }} == См. также == *[[Задача о наибольшей общей подпоследовательности]] == Источники информации ==*[https://en.wikipedia.org/wiki/Shortest_common_supersequence_problem Википедия — Shortest common supersequence problem] [[Категория:Дискретная математика и алгоритмы]][[Категория:Динамическое программирование]]