36
правок
Изменения
Добавлен псевдокод
[[Файл:Suffix-array2.png]]
==Псевдокод==
'''calc_positions'''('''vector''' &v)
//''преобразуем масив count''
'''for''' ('''int''' i = 1; i < count.size(); ++i)
count[i] += count[i - 1]
'''rotate'''(count, 1)
//''сдвигаем массив на 1 вправо для удобства работы с индексами''
count[0] = 0
//''теперь он содержит позиции в массиве suffs с которых ''
//''необходимо вставлять подстроки, начинающиеся с соответствующих символов''
'''suff_array'''(string &s)
s += '#'
//''На нулевом этапе сортируем подстроки длинной 1''
'''vector''' count(max('''int'''(alpha_size), s.length()))
//''count -- массив для сортировки подсчетом''
'''fill'''(count, 0)
'''for''' ('''int''' i = 0; i < s.length(); ++i)
++count[s[i]]
'''calc_positions'''(count)
'''vector''' suffs(s.length())
//''suffs будет хранить индексы начал отсортированных подстрок текущей длины''
'''for''' ('''int''' i = 0; i < s.length(); ++i)
suffs[count[ord(s[i])]++] = i
//''подстроки длинной 1 отсортированы''
//''разобьем их на классы эквивалентности''
'''vector'''<'''int'''> classes(s.length())
'''int''' classes_count = 0
'''char''' last_char = '#'
'''for''' ('''int''' i = 0; i < suffs.size(); ++i)
'''if''' s[suffs[i]] != last_char
last_char = s[suffs[i]]
++classes_count
classes[suffs[i]] = classes_count
//''нулевой этап завершен''
//''на следующих этапах сортируем подстроки длиной 2 * cur_len = 2^k''
'''for''' ('''int''' cur_len = 1; cur_len <= s.length(); cur_len *= 2)
//''сортируем по второй половине подстроки''
'''vector''' sorted_by2(s.length())
'''for''' ('''int''' i = 0; i < suffs.size(); ++i)
'''if''' suffs[i] < cur_len
sorted_by2[i] = suffs[i] + s_len - cur_len
'''else'''
sorted_by2[i] = suffs[i] - cur_len
//''теперь сортируем по первой половине''
//''сортировка стабильна, значит получим целиком отсортированные подстроки''
'''fill'''(count, 0)
'''for''' ('''int''' i = 0; i < sorted_by2.size() ++i)
++count[classes[sorted_by2[i]]]
'''calc_positions'''(count)
'''for''' ('''int''' i = 0; i < s.length(); ++i)
suffs[count[classes[sorted_by2[i]]]++] = sorted_by2[i]
//''Подстроки текущей длины отсортированы''
//''перещитаем классы эквивалентности''
'''vector''' new_classes(s.length())
new_classes[suffs[0]] = 0
classes_count = 0
'''for''' ('''int''' i = 1; i < new_classes.size(); ++i)
'''int''' mid1 = (suffs[i] + cur_len) % suffs.size()
'''int''' mid2 = (suffs[i-1] + cur_len) % suffs.size()
'''if''' (classes[suffs[i]] != classes[suffs[i-1]] || classes[mid1] != classes[mid2])
++classes_count
new_classes[suffs[i]] = classes_count
'''copy'''(new_classes, classes)//''сохраняем новые классы в classes''
'''return''' suffs
