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> x[i] = y[j] </tex>, то <tex>SCS</tex> для последовательностей <tex> x[1 \dots i] </tex> и <tex> y[1 \dots j] </tex> должна заканчиваться этим элементом, так как он общий для них. Получается следующее рекуррентное соотношение:
<tex>
<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> нужно минимизировать, значит имеет место равенство:
