Изменения

Последовательность <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> длину наименьшей общей суперпоследовательности для префиксов данных последовательностей <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>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}</tex> Cложность алгоритма составит <tex> O(mn) </tex>, где <tex> m </tex> и <tex> n </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[i - 1][j] > scs[i][j - 1] \\ 3, & 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>; <tex>prev[i][j]</tex> — массив для восстановления ответа.  ''<font color="green">// Подсчет динамики </font>'' '''fun''' SCS(x: '''int[]''', y: '''int[]'''): n = x.size m = y.size '' ''<font color="green">// инициализация массивов динамики </font>'' scs = '''int'''[][] pref = '''int'''[][] '' ''<font color="green">// случай равенства одного из индексов 0 </font>'' '''for''' i = 0 '''to''' n scs[i][0] = i '''for''' j = 0 '''to''' m scs[0][j] = j '' '''for''' i = 1 '''to''' n '''for''' j = 1 '''to''' m ''<font color="green">// случай равенства элементов </font>'' '''if''' x[i] == y[j] scs[i][j] = 1 + scs[i - 1][j - 1] prev[i][j] = 1 '''else''' ''<font color="green">// случай неравенства элементов </font>'' '''if''' scs[i - 1][j] > scs[i][j - 1] scs[i][j] = 1 + scs[i][j - 1] prev[i][j] = 2 '''else''' scs[i][j] = 1 + scs[i - 1][j] prev[i][j] = 3  ''<font color="green">// вывод SCS </font>'' '''fun''' printSCS(n: '''int''', m: '''int'''): i = n j = m ans = [] ''<font color="green">// массив ответа </font>'' '' '''while''' i > 0 '''and''' j > 0 '''if''' prev[i][j] == 1 ans.append(x[i]) i -= 1 j -= 1 '''else''' '''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] [[Категория:Дискретная математика и алгоритмы]][[Категория:Динамическое программирование]]