Изменения
→Псевдокод: записываем в строку s по индексу sa[i], а не по i
{{Определение
|definition=
'''Cуффиксным массивом''' (англ. ''suffix array'') строки <tex>s[1 .. n]</tex> называется массив <tex>suf</tex> целых чисел от <tex>1</tex> до <tex>n</tex>, такой, что суффикс <tex>s[suf[i]..n]</tex> — <tex>i</tex>-й в [[Лексикографический_порядок|лексикографическом ]] порядке среди всех непустых суффиксов строки <tex>s</tex>.}}
== Пример ==
Так как наш алфавит не ограничен, можно <tex>i</tex>-й в лексикографическом порядке суффикс сопоставить с <tex>i</tex>-й буквой в алфавите.
==== Доказательство корректности ====Если отсортировать суффиксы, то первые буквы будут расположены в том же порядке, как и в алфавите. ==== Псевдокод ==== '''string''' fromSuffixArrayToString('''int[]''' sa):
'''for''' i = 1 '''to''' n
s[sa[i]] = alphabet[i]
Для начала вместо каждого символа строки поставим символ из бесконечного алфавита в промежуточную строку <tex>tmp</tex>, как в решении выше. Пусть, мы рассматриваем <tex>i</tex>-й в лексикографическом порядке суффикс (т.е. и <tex>i</tex>-й символ строки). Его первый символ будет равен первому символу предущего в лексикографическом порядке суффикса, если <tex>tmp[sa[i - 1] + 1] < tmp[sa[i] + 1]</tex>, т.е. и их строки без первого символа так же в лексикографическом порядке. Иначе он должен быть больше, т.к. рассматриваемый суффикс следующий в лексикографическом порядке.
==== Пример ====Дан суффиксный массив <tex>[7, 5, 1, 3, 6, 2, 4]</tex>.Цветами показаны места, после которых добавляются новые символы. [[Файл:ExampleSuffixArray.png|center]] ==== Псевдокод ==== '''string''' fromSuffixArrayToString('''int[]''' sa):
'''for''' i = 1 '''to''' n
tmp[sa[i]] = alphabet[i]
cur = 1
s[sa[1]] = alphabet[1]
'''for''' i = 2 '''to''' n
j = sa[i - 1]
k = sa[i]
'''if''' tmp[j + 1] > tmp[k + 1]
cur++; s[sa[i]] = alphabet[cur]
'''return''' s
==== Доказательство минимальности ====
Докажем от противного. Пусть, есть решение в котором использовано меньше букв. Тогда найдется позиция в которой, наше решение отличается от минимального, причем в минимальном остается та же буква, как в предыдущем суффиксе, а в нашем появляется новая. Рассмотрим эти два подряд идущих суффикса. В решении выше добавится новая буква, только если продолжение первого суффикса лексикографически больше, чем продолжение второго. Получается, что в минимальном решении первый суффикс лексикографически больше, чем второй, что неверно. Пришли к противоречию.
== Применения ==
==См. также==
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
* [[Алгоритм Касаи и др.]]
==Примечания==
<references/>
== Источники ==
