Строки: суффиксный массив

Суффиксное дерево. Определение. Примеры использования.
Суффиксный массив. Построение с помощью сортировки.
Ускорение сортировки с помощью хешей.
Алгоритм построения за O(N log N)
Алгоритм Касаи
Примеры использования.
- нахождение подстроки
- нахождение наибольшего общего префикса
- подсчет числа различных подстрок
- нахождение наибольшей общей подстроки