63
правки
Изменения
м
→Связь с наибольшей общей подпоследовательностью
|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> так:
<tex> S = \dots x_1 \dots x_2 \dots x_i \dots x_n \dots </tex>
Мы должны поставить на место некоторых пропусков поставить элементы <tex>Y</tex>, так чтобы суммарная длина <tex> S </tex> была минимальна, и <tex> S </tex> был являлась суперпоследовательностью <tex>Y</tex>. Рассмотрим любую общую подпоследовательность <tex>X</tex> и <tex>Y</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>
