Изменения

Последовательность <tex> Z = \left \langle z_1, z_2, \dots, z_k \right \rangle </tex> является '''суперпоследовательностью''' (англ. ''supersequence'') последовательности <tex> X = \left \langle x_1, x_2, \dots, x_m \right \rangle </tex>, если существует ''строго возрастающая '' последовательность <tex> \left \langle i_1, i_2, \dots, i_m \right \rangle </tex> индексов <tex> Z </tex> таких, что для всех <tex> j = 1, 2, \dots, m </tex> выполняется соотношение <tex> z_{i_j} = x_j </tex>.

Последовательность <tex> Z </tex> является '''общей суперпоследовательностью''' (англ. ''common supersequence'') последовательностей <tex> X </tex> и <tex> Y </tex>, если <tex> X Z </tex> и является суперпоследовательностью как для <tex> Y X </tex> являются подпоследовательностями , так для и <tex> Z Y </tex>.

Пусть даны две последовательности длины <tex>n</tex> и <tex>m</tex> соответственно. Заметим, что если приписать к одной из данной последовательность данных последовательностей другую, то полученная последовательность будет их суперпоследовательностью с длиной <tex> n + m </tex>. Запомним все элементы обеих последовательностей и из них построим все возможные последовательности. Тогда искомая <tex>SCS</tex> гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.