Изменения

{{ОпределениеТеорема|definitionstatement=Последовательность <tex> Z |LCS(X, Y)| + |SCS(X, Y)| = n + m</tex> является ''', где <tex>|LCS(X, Y)|</tex> - длина [[Задача о наибольшей общей подпоследовательности| наибольшей общей подпоследовательностью''' подпоследовательности]], <tex>|SCS(англ. ''common subsequence''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>X</tex> являетcя подпоследовательностью <tex> S </tex>, то можно представить <tex>S</tex> так:<tex> S = \dots x_1 \dots x_2 \dots x_i \dots x_n \dots </tex>Мы должны поставить на место некоторых пропусков поставить элементы <tex>Y</tex>, так чтобы суммарная длина <tex> S </tex> была минимальна, и <tex> Y </tex> был подпоследовательностью <tex>S</tex>. Заметим, что если найдется подпоследовательность <tex> Z Y</tex> такая, что является подпоследовательностью как <tex> X </tex>, так и то все элементы этой подпоследовательности уже находятся в <tex>S</tex>, а значит их не нужно вставлять. Поэтому мы добавим не меньше чем <tex> m - |LCS(X, Y)| элементов </tex>. Длину <tex> SCS(X, Y) </tex> нужно минимизировать, значит имеет место равенство:<tex> |SCS(X,Y )| = n + (m - |LCS(X, Y)|)</tex>.Поэтому: <tex>|LCS(X, Y)| + |SCS(X, Y)| = n + m</tex>