1

Тема: Вопрос по алгоритму построения суффиксного массива

Здравствуйте.

Начал изучать суффиксный массив и застрял на массиве классов эквивалентности.

Не очень пойму для чего его вводят? Чему его элементы эквивалентны? Можно какой-нибудь пример конкретный. А то, как-то суть его не понятна. Ведь коды символов ровно так же распределяются как и массив эквивалентности.

По коду понятно, что он, как бы, заменяет символьный код. То есть на нулевом шаге мы коды символов использовали в качестве индексов подсчета

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;

Спасибо )