97
правок
Изменения
Нет описания правки
=== Псевдокод ===
'''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)
'''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''' c['''compare1'''(j1] - c[, j2])
'''else'''
'''return''' c['''compare1'''(j1 + l] - c[, j2 + l) ==См. также==[[Алгоритм цифровой сортировки суффиксов циклической строки]]
==Источники информации==
