418
правок
Изменения
Нет описания правки
else
PrintLCS(b, X, i, j - 1)
== Оптимизация для вычисления только длины НОП ==
Заметим, что для вычисления <tex> a[i][j] </tex> нужны только <tex> i </tex>-ая и <tex> (i-1) </tex>-ая строчки матрицы <tex> a </tex>. Тогда можно использовать лишь <tex> 2 \cdot min(m, n) </tex> элементов таблицы:
LCS2(X, Y)
if length(X) < length(Y) // в таблице будет length(Y) столбцов, и если length(X) меньше, выгоднее поменять местами X и Y
swap(X, Y)
m = length(X)
n = length(Y)
for j = 0 to n
a[0][j] = 0
a[1][j] = 0
for i = 1 to m
a[1][0] = 0
for j = 1 to n
a[0][j] = a[1][j] // элемент, который был в a[1][j], теперь в предыдущей строчке
if x[i] = y[i]
a[1][j] = a[0][j - 1] + 1
else
if a[0][j] >= a[1][j - 1]
a[1][j] = a[0][j]
else
a[1][j] = a[1][j - 1]
// ответ — a[1][n]
Приглядевшись повнимательнее, заметим, что от <tex> (i - 1) </tex>-ой строчки нам нужны только элементы с <tex> (j - 1) </tex>-го столбца. В этом случае можно использовать лишь <tex> min(m, n) </tex> элементов таблицы:
LCS3(X, Y)
if length(X) < length(Y) // в таблице будет length(Y) столбцов, и если length(X) меньше, выгоднее поменять местами X и Y
swap(X, Y)
m = length(X)
n = length(Y)
for j = 0 to n
a[j] = 0
d = 0 // d — дополнительная переменная, в ней хранится a[i - 1][j - 1]
// в a[j], a[j + 1], …, a[n] хранятся a[i - 1][j], a[i - 1][j + 1], …, a[i - 1][n]
// в a[0], a[1], …, a[j - 1] хранятся a[i][0], a[i][1], …, a[i][j - 1]
for i = 1 to m
for j = 1 to n
tmp = a[j]
if x[i] = y[i]
a[j] = d + 1
else
if a[j] >= a[j - 1]
a[j] = a[j] // в a[j] и так хранится a[i - 1][j]
else
a[j] = a[j - 1]
d = tmp
// ответ — a[n]
== Список литературы ==
Т. Кормен, Ч. Лейзерсон, Р. Риверст, К. Штайн, «Алгоритмы: построение и анализ», 2-е изд., стр 418—425
