36
правок
Изменения
м
→Псевдокод
//''преобразуем масив 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 += '#$'; int alpha_size = 255;
//''На нулевом этапе сортируем подстроки длиной 1''
'''vector''' count(max(alpha_size, s.length()));
//''count -- массив для сортировки подсчетом''
'''fill'''(count, 0);
'''for''' ('''int''' i = 0; i < s.length(); ++i)
++count[ord(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.length() - 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];
//''Подстроки текущей длины отсортированы''
//''переcчитаем классы эквивалентности''
'''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;
