Изменения

Перейти к: навигация, поиск

Задача о наименьшей суперпоследовательности

97 байт добавлено, 17:56, 27 декабря 2017
Псевдокод
<tex> x, y</tex> — данные последовательности; <tex>scs[i][j] </tex> — <tex>SCS</tex> для префикса длины <tex>i</tex> последовательности <tex>x</tex> и префикса длины <tex>j</tex> последовательности <tex>y</tex>; <tex>prev[i][j]</tex> — массив для восстановления ответа.
''<font color="green">// Подсчет динамики </font>''
'''fun''' SCS(x: '''int''', y: '''int'''):
n = x.size
scs[i][j] = 0
prev[i][j] = 0
''<font color="green">//случай равенства одного из индексов 0 </font>''
'''for''' i = 0 '''to''' n
scs[i][0] = i
prev[i][j] = 3
''<font color="green">//вывод SCS </font>''
'''fun''' printSCS(n: '''int''', m: '''int'''):
i = n
ans.append(x[i])
i -= 1
''<font color="green">// добавляем оставшиеся символы первой последовательности </font>''
'''while''' i > 0
ans.append(x[i])
i -= 1
''<font color="green">// добавляем оставшиеся символы второй последовательности </font>''
'''while''' j > 0
ans.append(y[j])
63
правки

Навигация