97
правок
Изменения
→Псевдокод
==Псевдокод==
<font color=darkgreen>/* преобразует масив count, так что
теперь он содержит позиции в массиве suffs с которых
необходимо вставлять подстроки, начинающиеся с соответствующих символов */</font> '''calc_positionsint[]'''calc_positions(count)
count[0] = 0
'''for''' i = 2 .. count.length
count[i] += count[i - 1]
'''return''' count
<font color=darkgreen>/* принимает строку, для которой требуется построить суффиксный массив возвращает суффиксный массив */</font> '''suff_arrayint[]'''suff_array(str)
s += '$'
''ALPHABET '' = 255
<font color=darkgreen>// нулевая итерация</font> count = '''int'''[max(''ALPHABET'', str.length)]
'''fill'''(count, 0)
'''for''' ch '''in''' str
count[ch]++
count = '''calc_positions'''(count) <font color=darkgreen>// suffs будет хранить индексы начал отсортированных подстрок текущей длины</font>
suffs = '''int'''[str.length]
'''for''' ch '''in''' str
classes[suf] = classesN;
<font color=darkgreen>// нулевая итерация завершена // сортируем подстроки длиной 2 * cur_len = 2^k</font>
curr_len = 1
'''while''' cur_len <= tex> \leqslant </tex> str.length <font color=darkgreen>// сортируем по второй половине подстроки</font>
sorted_by2 = '''int'''[str.length]
'''for''' i = 0 .. str.length
sorted_by2[i] = (suffs[i] + str.length - cur_len) % str.length
<font color=darkgreen>// сортируем по первой половине // сортировка устойчивая, значит получим целиком отсортированные подстроки</font>
'''fill'''(count, 0)
'''for''' by2 '''in''' sorted_by2
count[classes[by2]]++
count = '''calc_positions'''(count)
'''for''' i = 0 .. str.length
suffs[count[classes[sorted_by2[i]]]++] = sorted_by2[i]
