16
правок
Изменения
Нет описания правки
{{Задача
|definition=
Задача нахождения '''наибольшей общей подпоследовательности''' (''longest common subsequence, LCS'') — это задача поиска последовательности, которая является самой длинной подпоследовательностью нескольких последовательностей (обычно двух).
}}
== Определения ==
<tex> x </tex>, <tex> y </tex> — данные последовательности; <tex> lcs[i][j] </tex> — LCS для префикса длины <tex> i </tex> последовательности <tex> x </tex> и префикса длины <tex> j </tex> последовательности <tex> y </tex>; <tex> prev[i][j] </tex> — пара индексов элемента таблицы, соответствующего оптимальному решению вспомогательной задачи, выбранной при вычислении <tex> lcs[i][j] </tex>.
LCS(x, y)
m = length(x)
n = length(y)
'''for ''' i = 1 to m
lcs[i][0] = 0
'''for ''' j = 0 to n
lcs[0][j] = 0
'''for ''' i = 1 to m '''for ''' j = 1 to n '''if ''' x[i] == y[j]
lcs[i][j] = lcs[i - 1][j - 1] + 1
prev[i][j] = pair(i - 1, j - 1)
'''else''' '''if ''' lcs[i - 1][j] >= lcs[i][j - 1]
lcs[i][j] = lcs[i - 1][j]
prev[i][j] = pair(i - 1, j)
'''else'''
lcs[i][j] = lcs[i][j - 1]
prev[i][j] = pair(i, j - 1)
printLCS(prev, x, i, j)
'''if ''' i == 0 or j == 0 ''<font color="green">// пришли к началу НОП</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 - 1, j - 1)
print x[i]
'''else''' '''if ''' prev[i][j] == pair(i - 1, j)
printLCS(prev, x, i - 1, j)
'''else'''
printLCS(prev, x, i, j - 1)
LCS2(x, y)
'''if ''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>''
swap(x, y)
m = length(x)
n = length(y)
'''for ''' j = 0 to n
lcs[0][j] = 0
lcs[1][j] = 0
'''for ''' i = 1 to m
lcs[1][0] = 0
'''for ''' j = 1 to n lcs[0][j] = lcs[1][j] ''<font color="green">// элемент, который был в a[1][j], теперь в предыдущей строчке</font>'' '''if ''' x[i] == y[j]
lcs[1][j] = lcs[0][j - 1] + 1
'''else''' '''if ''' lcs[0][j] >= lcs[1][j - 1]
lcs[1][j] = lcs[0][j]
'''else'''
lcs[1][j] = lcs[1][j - 1]
''<font color="green">// ответ — lcs[1][n]</font>''
Также можно заметить, что от <tex> (i - 1) </tex>-ой строчки нужны только элементы с <tex> (j - 1) </tex>-го столбца. В этом случае можно использовать лишь <tex> min(m, n) </tex> элементов таблицы:
LCS3(x, y)
'''if ''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>''
swap(x, y)
m = length(x)
n = length(y)
'''for ''' j = 0 to n
lcs[j] = 0
d = 0 ''<font color="green">// d — дополнительная переменная, в ней хранится lcs[i - 1][j - 1]'' ''// в lcs[j], lcs[j + 1], …, lcs[n] хранятся lcs[i - 1][j], lcs[i - 1][j + 1], …, lcs[i - 1][n]'' ''// в lcs[0], lcs[1], …, lcs[j - 1] хранятся lcs[i][0], lcs[i][1], …, lcs[i][j - 1]</font>'' '''for ''' i = 1 to m '''for ''' j = 1 to n
tmp = lcs[j]
'''if ''' x[i] == y[i]
lcs[j] = d + 1
'''else''' '''if ''' lcs[j] >= lcs[j - 1] lcs[j] = lcs[j] ''<font color="green">// в lcs[j] и так хранится lcs[i - 1][j]</font>'' '''else'''
lcs[j] = lcs[j - 1]
d = tmp
== Список литературы ==
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
