16
правок
Изменения
Нет описания правки
{{Определение
|definition=
{{Задача
|definition=
}}
== Наивное решение ==
== Динамическое программирование ==
=== Доказательство оптимальности ===
''<font color="green">// подсчёт таблиц</font>''
'''int''' LCS(x: '''int''', y : '''int'''):
m = length(x)
n = length(y)
''<font color="green">// вывод LCS, вызывается как printLCS(m, n)</font>''
'''int''' printLCS(i: '''int''', j: '''int'''):
'''if''' i == 0 '''or''' j == 0 ''<font color="green">// пришли к началу LCS</font>''
'''return'''
Заметим, что для вычисления <tex> lcs[i][j] </tex> нужны только <tex> i </tex>-ая и <tex> (i-1) </tex>-ая строчки матрицы <tex> lcs </tex>. Тогда можно использовать лишь <tex> 2 \cdot min(m, n) </tex> элементов таблицы:
'''int''' LCS2(x: '''int''', y: '''int'''):
'''if''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>''
swap(x, y)
Также можно заметить, что от <tex> (i - 1) </tex>-ой строчки нужны только элементы с <tex> (j - 1) </tex>-го столбца. В этом случае можно использовать лишь <tex> min(m, n) </tex> элементов таблицы:
'''int''' LCS3(x: '''int''', y: '''int'''):
'''if''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>''
swap(x, y)
== Длина кратчайшей общей суперпоследовательности ==
Для двух подпоследовательностей <tex>X_{m - 1}</tex> и <tex>Y_{n - 1}</tex> длина кратчайшая общей суперпоследовательности равна
<tex>
|SCS(X,Y)| = n + m - |LCS(X,Y)|
