Изменения

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

В <tex> scs[i][j] </tex> помимо длины последовательности хранятся хранится и символ, добавленный последним. Таким образом, зная длину SCS, можно восстановить и саму последовательность.