63
правки
Изменения
Нет описания правки
== Наивное решение ==
Заметим, что если приписать к одной из данной последовательность другую, то полученная последовательность будет их суперпоследовательностью с длиной <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>, то SCS должна включать оба этих элемента. Значит нужно выбрать оптимальный из ответов для префиксов, включающих один элемент и не включающих второй, и выбрать из них минимальный. Если же <tex> x[i] = y[j] </tex>, то SCS для последовательностей <tex> x[1 \dots i] </tex> и <tex> y[1 \dots j] </tex> должна заканчиваться этим элементом, так как он общий для них. Получается следующее рекуррентное соотношение:
<tex>
scs[i][j] =
\begin{cases}
i, & j = 0 \\
j, & i = 0 \\
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>
