63
правки
Изменения
м
Нет описания правки
{{
Теорема|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> их <tex>SCS</tex> и будем ее строить. Так как <tex>S</tex> являетcя суперпоследовательностью <tex> X </tex>, то можно представить <tex>S</tex> так:
