Теорема 1 показывает, что нахождением НОП последовательностей и сводится к решению либо одной, либо двух подзадач. Если , то достаточно найти НОП последовательностей и дописать к ней в конце . Если же , то надо решить две подзадачи: найти НОП для , а затем найти НОП для . Более длинная из них и будет служить НОП для
Видно, что возникает перекрытие подзадач.
Чтобы найти НОП нам может понадобиться найти НОП и НОП ; каждая из этих задач содержит подзадачу нахождения НОП для
Обозначение
C[i, j] – длина НОП для последовательностей
Рекуррентное соотношение для c[i,j]
0, если i = 0 или j =0,
c[i-1,j-1]+1, если i, j >0 и xi = yj
max (c[i,j-1], c[i-1 ,j]), если i, j >0 и xi ≠ yj
Вычисление длины НОП
Так как различных подзадач всего Θ (mn) для решения задачи лучше использовать динамическое программирование.
Исходные данные:
последовательности X = x1, x2, . . . xm
и Y = y1, y2, . . . yn
результат:
таблицы c [0..m,0..n] и b[1..m,1..n]
LCS-LENGTH (X,Y)
1 m ¬ length[X]
2 n ¬ length[Y]
3 for i ¬ 1 to m
4 do c[i,0] ¬ 0
5 for j ¬ 1 to n
6 do c[0,j] ¬ 0
7 for i ¬ 1 to m
8 do for j ¬ 1 to n
9 do if xi = yj
10 then c[i,j] ¬ c[i-1,j-1]+1
11 b[i,j] ¬ “ ”
12 else ifc[i-1,j] ≥ c[i,j-1]
13 then c[i,j] ¬ c[i-1,j]
14 b[i,j] ¬ “ ↑ ”
15 else c[i,j] ¬ c[i,j-1]
16 b[i,j] ¬ “ ← ”
17 return c,b
Построение НОП
PRINT-LCS (b,X,i,j)
1 if i= 0 или j = 0