Тема: Вопрос по алгоритму построения суффиксного массива
Здравствуйте.
Начал изучать суффиксный массив и застрял на массиве классов эквивалентности.
Не очень пойму для чего его вводят? Чему его элементы эквивалентны? Можно какой-нибудь пример конкретный. А то, как-то суть его не понятна. Ведь коды символов ровно так же распределяются как и массив эквивалентности.
По коду понятно, что он, как бы, заменяет символьный код. То есть на нулевом шаге мы коды символов использовали в качестве индексов подсчета
cnt[s[i]]
, а далее по коду видно, что используется
cnt[c[pn[i]]]
. Разве нельзя использовать вот это же
cnt[s[i]]
, типа
cnt[s[pn[i]]]
?
И не уловил для чего считается вот это:
int mid1 = (p[i] + (1<<h)) % n, mid2 = (p[i-1] + (1<<h)) % n;
Спасибо )