63
правки
Изменения
Нет описания правки
== Динамическое программирование ==
===Решение===
Обозначим за <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>, то SCS должна включать оба этих элемента. Значит нужно выбрать оптимальный из ответов для префиксов, включающих один элемент и не включающих второй, и выбрать из них минимальный. Если же <tex> x[i] = y[j] </tex>, то SCS для последовательностей <tex> x[1 \dots i] </tex> и <tex> y[1 \dots j] </tex> должна заканчиваться этим элементом, так как он общий для них. Получается следующее рекуррентное соотношение:
i, & j = 0 \\
j, & i = 0 \\
1 + scs[i - 1][j - 1] + 1, & x[i] = y[j] \\
1 + min(scs[i][j - 1],\ scs[i - 1][j]), & x[i] \neq y[j]
\end{cases}
</tex>
Очевидно, что сложность алгоритма составит <tex> O(mn) </tex>, где <tex> m </tex> и <tex> n </tex> — длины последовательностей.
===Восстановление ответа===
В <tex> scs[i][j] </tex> помимо длины последовательности хранятся и символ, добавленный последним. Таким образом, зная длину SCS, можно восстановить и саму последовательность.
===Псевдокод===
x, y — данные последовательности; scs[i][j] — SCS для префикса длины i последовательности x и префикса длины j последовательности y; prev[i][j] — пара индексов элемента таблицы, соответствующего оптимальному решению вспомогательной задачи, выбранной при вычислении scs[i][j].
