97
правок
Изменения
→Псевдокод
теперь он содержит позиции в массиве suffs с которых
необходимо вставлять подстроки, начинающиеся с соответствующих символов */</font>
'''int[]''' calc_positions('''int[]''' count)
count[0] = 0
'''for''' i = 2 .. count.length
<font color=darkgreen>/* принимает строку, для которой требуется построить суффиксный массив
возвращает суффиксный массив */</font>
'''int[]''' suff_array('''string''' str)
s += '$'
<font color=darkgreen>// нулевая итерация</font>
count = '''int'''[max(''ALPHABET''<tex>|\Sigma|</tex>, str.length)]
'''fill'''(count, 0)
'''for''' ch '''in''' str
sorted_by2 = '''int'''[str.length]
'''for''' i = 0 .. str.length
sorted_by2[i] = (suffs[i] + str.length - cur_len) % '''mod''' str.length
<font color=darkgreen>// сортируем по первой половине
// сортировка устойчивая, значит получим целиком отсортированные подстроки</font>
classesN = 0
'''for''' i = 0 .. str.length
mid1 = (suffs[i] + cur_len) % '''mod''' str.length mid2 = (suffs[i - 1] + cur_len) % '''mod''' str.length
'''if''' classes[suffs[i]] <tex> \neq </tex> classes[suffs[i-1]] '''or''' classes[mid1] <tex> \neq </tex> classes[mid2]
classesN
