63
правки
Изменения
→Псевдокод
== Динамическое программирование ==
===Решение===
Обозначим за <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>
<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[]'''): ''<font color="green">// аналог void </font>''
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]
scs[i][j] = 1 + scs[i - 1][j]
prev[i][j] = 3
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
'''while''' i > 0 ''<font color="green">// добавляем оставшиеся символы первой последовательности </font>'' '''while''' i > 0
ans.append(x[i])
i -= 1
''<font color="green">// добавляем оставшиеся символы второй последовательности </font>''
'''while''' j > 0
ans.append(y[j]) ''<font color="green">// добавляем оставшиеся символы второй последовательности </font>''
j -= 1
''
'''reverse'''(ans) ''<font color="green">// разворачиваем последовательность, так как шли с конца </font>''
'''return''' ans
|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>
