Изменения
→Алгоритм, использующий префиксы циклических сдвигов: Исправил код compare2
=== Псевдокод ===
'''int[]''' suf_arraysufArray('''string''' s)
suf = {0, 1 .. s.length}
'''sort'''(suf, compare)
'''return''' suf
'''intorder''' compare ('''int''' j1, '''int''' j2)
'''for''' i = 0 .. s.length
'''if''' (s[(j1 + i) '''mod''' s.length] > s[(j2 + i) '''mod''' s.length])
'''return''' 1''GT''
'''if''' (s[(j1 + i) '''mod''' s.length] < s[(j2 + i) '''mod''' s.length])
'''return''' -1''LT'' '''return''' 0''EQ''
== Алгоритм, использующий хеши ==
=== Псевдокод ===
'''int[]''' suf_arraysufArray('''string''' s)
suf = {0, 1 .. s.length}
'''sort'''(suf, compare)
'''return''' suf
'''intorder''' compare ('''int''' j1, '''int''' j2) same = '''lcp'''(j1, j2) '''if''' s[j1 + same] < s[j2 + same] '''return''' ''LT'' '''else if''' s[j1 + same] - s== s2[j2 + same] '''return''' ''EQ'' '''else''' '''return''' ''GT''
'''int''' lcp (j1, j2)
l = -1
r = s.length + 1
Схожая идея используется и в [[Алгоритм цифровой сортировки суффиксов циклической строки|алгоритме цифровой сортировки суффиксов циклической строки]], который имеет лучшую асимптотику.
=== Псевдокод ===
'''int[]''' suf_array('''string''' s)
suf = {0, 1 .. s.length}
'''sort'''(suf, compare1)
l2 = suf[i]
r2 = suf[i] + l
'''if''' (c[l1] <tex>\neq</tex> c[l2] '''or''' c[r1] <tex>\neq</tex> c[r2])
c'[suf[i]] = c'[suf[i - 1]] + 1
'''else'''
'''return''' suf
'''intorder''' compare1 ('''int''' j1, '''int''' j2) '''if''' s[j1] < s[j2] '''return''' ''LT'' '''else if''' s[j1] - == s[j2] '''return''' ''EQ'' '''else''' '''return''' ''GT''
'''intorder''' compare2 ('''int''' j1, '''int''' j2)
'''if''' c[j1] <tex>\neq</tex> c[j2]
'''return''' '''compare'''(c[j1] - , c[j2])
'''else'''
'''return''' '''compare'''(c[j1 + l] - , c[j2 + l]) ==См. также==* [[Суффиксный массив]]* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
==Источники информации==
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Суффиксный массив]]
