63
правки
Изменения
Нет описания правки
{{Задача
|definition=
Пусть имеются последовательности <tex> X = \left \langle x_1, x_2, \dots, x_n \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, \dots, y_m \right \rangle </tex>. Необходимо найти <tex>SCS(X,Y)</tex>, где <tex>SCS(X, Y)</tex> - — '''наименьшая общая суперпоследовательность''' (англ. ''shortest common supersequence'') последовательностей <tex> X </tex> и <tex> Y </tex>
}}
{{
Теорема|statement=
<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> их SCS и будем ее строить. Так как <tex>S</tex> являетcя суперпоследовательностью <tex> X </tex>, то можно представить <tex>S</tex> так:
