</tex>
Очевидно, что сложность Cложность алгоритма составит <tex> O(mn) </tex>, где <tex> m </tex> и <tex> n </tex> — длины последовательностей.
===Восстановление ответа===
В Для восстановления ответа заведем массив <tex> prev[0 \dots n][0\dots m] </tex>, где <tex>prev[i][j]</tex> будет означать индексы в массиве <tex> scs</tex>, при которых достигалось наименьшее значение <tex>sc[i][j] </tex> помимо длины последовательности хранится и символ, добавленный последним. Таким образом, зная длину SCS, можно восстановить и саму последовательность.
===Псевдокод===
prev[i][j] = pair(i, j - 1)
'''fun''' printLCS(mn: '''int''', nm: '''int'''): ''<font color="green">// вывод SCS</font>'' i = mn j = nm
ans = [] ''<font color="green">// массив ответа </font>''
'''while''' i > 0 '''and''' j > 0
