79
правок
Изменения
Восстановление строки по суффиксному массиву
Значит, суффиксный массив для строки <tex>s</tex> равен <tex>[7, 5, 1, 3, 6, 2, 4]</tex>.
== Восстановление строки по суффиксному массиву ==
=== Постановка задачи ===
Дан суффиксный массив некоторой строки <tex>s</tex>, необходимо восстановить строку за время <tex>O(|s|)</tex>.
=== Вариант для бесконечного алфавита ===
Так как наш алфавит не ограничен, можно <tex>i</tex>-й в лексикографическом порядке суффикс сопоставить с <tex>i</tex>-й буквой в алфавите.
=== Псевдокод ===
'''string''' ('''int[]''' sa):
'''for''' i = 1 '''to''' n
s[sa[i]] = alphabet[i]
'''return''' s
=== Вариант для минимально возможного ===
Для начала вместо каждого символа строки поставим символ из бесконечного алфавита в промежуточную строку <tex>tmp</tex>, как в решении выше. Пусть, мы рассматриваем <tex>i</tex>-й в лексикографическом порядке суффикс (т.е. и i-ый символ строки). Его первый символ будет равен первому символу предущего в лексикографическом порядке суффикса, если tmp[sa[i - 1] + 1] < tmp[sa[i] + 1], т.е. и их строки без первого символа так же в лексикографическом порядке. Иначе он должен быть больше, т.к. рассматриваемый суффикс следующий в лексикографическом порядке.
=== Псевдокод ===
'''string''' ('''int[]''' sa):
'''for''' i = 1 '''to''' n
tmp[sa[i]] = alphabet[i]
cur = 1
s[1] = alphabet[1];
'''for''' i = 2 '''to''' n
j = sa[i - 1];
k = sa[i];
'''if''' tmp[j + 1] > tmp[k + 1]
cur++;
s[i] = alphabet[cur]
'''return''' s
== Применения ==
