Пост может быть полезен только для div2 .

Вчера я пытался отвечать на вопросы в комментариях к посту о построении массива LCP по суффиксному массиву (алгоритм Касаи). http://codeforces.com/blog/entry/12796

У алгоритма есть определённые тонкости реализации , которые можно понять неправильно, когда вы впервые встречаетесь с ним.

Я попробую развеять все неясности здесь.

Алгоритм в основном цикле рассматривает суффиксы в том порядке, в котором они идут в исходной строке.

Сначала str[0:n], затем str[1:n], затем s[2:n] и так далее.

Если посмотреть на реализацию, то может показаться, что это не так и алгоритм рассматривает суффиксы в порядке сортировки , после прочтения строки j=sa[rank[i] + 1].

На самом деле происходит следующее.

Элемент суффиксного массива под номером X, sa[X], даёт номер Y суффикса в строке str, который идёт в отсортированном списке под номером X .

Так как rank[i] -- это обратная функция к суффиксному массиву, то rank[i] дает такое число Z , что sa[Z] =i, то есть даёт номер i -го суффикса в суффиксном массиве.

Тогда j=sa[rank[i] + 1] -- это позиция в исходной строке, на которой начинается следующий за i -м в порядке сортировки суффикс.

Затем суффиксы тривиальным образом сравниваются за пределами неизвестной части (как в более простых O(n) строковых алгоритмах, таких как префикс — функция или алг-м Манакера).

И полученное значение присваивается не i -му элементу массива lcp , а элементу под номером равным номеру rank[i] i -го суффикса в порядке сортировки, как и "должно быть", потому что LCP показывает длину совпадающей части между двумя соседними суффиксами именно в порядке лексикографической сортировки, а не в порядке их следования в исходной строке.