Строки: суффиксные структуры (23 марта 2015)

1. Алгоритм построения сжатого суфф.дерева по суфф.массиву+LCP за O(n).
2. Суфф дерево → суфф массив + LCP
3. Задачи на суфф.структуры (суфф.массив, суфф.дерево)
1. Поиск слова в тексте
2. Количество подстрок
3. refrain: длина * количество вхождения → max
4. Общая подстрока двух строк, k строк.
5. [не успеем] LCP = Наибольший общий префикс = LCA в суффиксном дереве.
6. [не успеем] Подпалиндром. Максимальный по длине. Количество.
7. [не успеем] Общий подпалиндром.
8. [не успеем] Два самых длинных неперекрывающихся вхождения.
9. [не успеем] k-я подстрока строки