63
правки
Изменения
Нет описания правки
===Восстановление ответа===
Для восстановления ответа заведем массив <tex> prev[0 \dots n][0\dots m] </tex>, где <tex>prev[i][j]</tex> будет означать индексы в массиве равняться: <tex>scs</texprev[i][j] =\begin{cases} 1, & x[i] == y[j] \\ 2, & x[i] \neq y[j], sc[i - 1][j] >sc[i][j - 1] \\ 3, при которых достигалось наименьшее значение & x[i] \neq y[j], sc[i - 1][j] <tex>scssc[i][j- 1]\\ \end{cases}</tex> По этим данным можно узнать, какой символ был добавлен в наименьшую общую суперпоследовательность.
===Псевдокод===
'''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)2
'''else'''
scs[i][j] = 1 + scs[i][j - 1]
prev[i][j] = pair(i, j - 1)3
'''fun''' printLCS(n: '''int''', m: '''int'''): ''<font color="green">// вывод SCS</font>''
ans = [] ''<font color="green">// массив ответа </font>''
'''while''' i > 0 '''and''' j > 0
'''if''' prev[i][j] == pair(i - 1, j - 1)
ans.append(x[i])
i -= 1
j -= 1
'''else'''
'''if''' prev[i][j] == pair(i - 1, j)2
ans.append(x[i])
i -= 1
