Бюрократы, editor, Администраторы
422
правки
Изменения
м
→Алгоритм за O(N log^2(N)) (префиксы циклических сдвигов)
В начале легко можно отсортировать за <tex>O(N \log(N))</tex> префиксы длины <tex>1</tex>, т.е. символы. А номера классов поставить в соответствии с порядковым номером символа в алфавите.
Рассмотрим теперь переход от префиксов длины <tex>l</tex> к префиксам длины <tex>2l</tex>. Научимся сравнивать два префикса длины <tex>2l</tex> за <tex>O(1)</tex>: Пусть даны префиксы <tex>s[i..i+2l-1]</tex>, <tex>s[j..j+2l-1]</tex>, сравним сначала их левые половинки, использовав значения <tex>c[i], c[j]</tex> с предыдущего шага, если <tex>c[i]\neq c[j]</tex>, то префиксы соотносятся так как же, как <tex>c[i]</tex> и <tex> c[j]</tex>, если <tex>c[i]=c[j]</tex>, то переходим к сравнению <tex>c[i+l]</tex> и <tex> c[j+l]</tex>. И так Итак, отсортировать префиксы длины <tex>2l</tex> можно за <tex>O(N\log(n))</tex>. Вычислить новые <tex>c[i]</tex> можно легко просто пробежавшись в лексикографическом порядке по префиксам, и увеличивая значение соответствующего класса на <tex>1</tex> если текущий префикс не совпадает с предыдущим (сравнивать с помощью старых <tex>c[i], c[i+l]</tex>).
После шага <tex>l =2^{\lceil \log_2(n)\rceil} \ge N</tex>. Все циклические сдвиги будут отсортированы. Всего шагов <tex>O(\log(N))</tex>, каждый шаг проводится за <tex>O(N \log(n))</tex>, итоговая асимптотика <tex>O(N \log^2(N))</tex>.
