16
правок
Изменения
Нет описания правки
{{
Теорема|statement=
Пусть имеются последовательности <tex> X = \left \langle x_1, x_2, ..., x_m \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, ..., y_n \right \rangle </tex>, а <tex> Z = \left \langle z_1, z_2, ..., z_k \right \rangle </tex> — их НОПLCS.
# Если <tex> x_m = y_n </tex>, то <tex> z_k = x_m = y_n </tex> и <tex> Z_{k - 1} </tex> — НОП LCS <tex> X_{m - 1} </tex> и <tex> Y_{n - 1} </tex># Если <tex> x_m \neq y_n </tex>, то из <tex> z_k \neq x_m </tex> следует, что <tex> Z </tex> — НОП LCS <tex> X_{m - 1} </tex> и <tex> Y </tex># Если <tex> x_m \neq y_n </tex>, то из <tex> z_k \neq y_n </tex> следует, что <tex> Z </tex> — НОП LCS <tex> X </tex> и <tex> Y_{n - 1} </tex>
|proof=
# Если бы выполнялось <tex> z_k \neq x_m </tex>, то к <tex> Z </tex> можно было бы добавить элемент <tex> x_m = y_n </tex>, и тогда получилась бы общая подпоследовательность длины <tex> k + 1 </tex>, что противоречит предположению, что <tex> Z </tex> — НОПLCS. Значит, выполняется <tex> z_k = x_m = y_n </tex>. Значит, <tex> Z_{k - 1} </tex> — общая подпоследовательность <tex> X_{m - 1} </tex> и <tex> Y_{n - 1} </tex>. Докажем от противного, что <tex> Z_{k - 1} </tex> — НОПLCS: тогда есть общая подпоследовательность <tex> W </tex>, длина которой больше <tex> k - 1 </tex>. Добавив к <tex> W </tex> элемент <tex> x_m = y_n </tex>, получим НОП LCS <tex> X </tex> и <tex> Y </tex>, длина которой больше <tex> k </tex> (т.е. больше длины <tex> Z </tex>), что приводит к противоречию.# Если <tex> z_k \neq x_m </tex>, то <tex> Z </tex> — общая подпоследовательность <tex> X_{m - 1} </tex> и <tex> Y </tex>. Пусть существует их общая подпоследовательность <tex> W </tex>, длина которой превышает <tex> k </tex>. Она также является общей подпоследовательностью <tex> X </tex> и <tex> Y </tex>, что противоречит предположению о том, что <tex> Z </tex> (длины <tex> k </tex>) — НОП LCS <tex> X </tex> и <tex> Y </tex>.
# Аналогично второму случаю.
}}
=== Решение ===
Обозначим как <tex> lcs[i][j] </tex> НОП LCS префиксов данных последовательностей, заканчивающихся в элементах с номерами <tex> i </tex> и <tex> j </tex> соответственно. Получается следующее рекуррентное соотношение:
<tex>
=== Построение подпоследовательности ===
Для каждой пары элементов помимо длины LCS соответствующих префиксов хранятся и номера последних элементов, участвующих в этой НОПLCS.Таким образом, посчитав ответ, можно восстановить всю наибольшую общую подпоследовательность.
=== Псевдокод ===
prev[i][j] = pair(i, j - 1)
''<font color="green">// вывод НОПLCS, вызывается как printLCS(prev, x, m, n)</font>''
printLCS(prev, x, i, j)
'''if''' i == 0 or j == 0 ''<font color="green">// пришли к началу НОПLCS</font>''
'''return'''
'''if''' prev[i][j] == pair(i - 1, j - 1) ''<font color="green">// если пришли в lcs[i][j] из lcs[i - 1][j - 1], то x[i] == y[j], надо вывести этот элемент</font>''
printLCS(prev, x, i, j - 1)
== Оптимизация для вычисления только длины НОП LCS ==
Заметим, что для вычисления <tex> lcs[i][j] </tex> нужны только <tex> i </tex>-ая и <tex> (i-1) </tex>-ая строчки матрицы <tex> lcs </tex>. Тогда можно использовать лишь <tex> 2 \cdot min(m, n) </tex> элементов таблицы:
