Изменения

x, y — данные последовательности; <tex>scs[i][j] </tex> — SCS для префикса длины i последовательности x и префикса длины j последовательности y; prev[i][j] — пара индексов элемента таблицы, соответствующего оптимальному решению вспомогательной задачикоторые предшествовали <tex>scs[i][j]</tex>.  '''fun''' SCS(x: '''int''', выбранной при вычислении y: '''int'''): ''<font color="green">// аналог void </font>'' m = x.size n = y.size '''for''' i = 1 '''to''' m scs[i][0] = i '''for''' j = 0 '''to''' n scs[0][j] = j '''for''' i = 1 '''to''' m '''for''' j = 1 '''to''' n '''if''' x[i]== y[j]. scs[i][j] = 1 + scs[i - 1][j - 1] prev[i][j] = pair(i - 1, j - 1) '''else''' '''if''' scs[i - 1][j] <= lcs[i][j - 1] scs[i][j] = 1 + scs[i - 1][j] prev[i][j] = pair(i - 1, j) '''else''' scs[i][j] = 1 + scs[i][j - 1] prev[i][j] = pair(i, j - 1) '''int''' printLCS(m: '''int''', n: '''int'''): ''<font color="green">// вывод SCS, вызывается как printLCS(m, n)</font>'' '''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(i - 1, j - 1) print x[i] '''else''' '''if''' prev[i][j] == pair(i - 1, j) printLCS(i - 1, j) '''else''' printLCS(i, j - 1)