Строки-5, суффиксный массив (28 апреля)

1. Поиск строки в тексте
1. С помощью суффиксного дерева за O(|s|)
2. С помощью суффиксного массива за O(|s|log|t|)
3. С помощью суффиксного массива за O(|s| + log|s|log|t|)
4. С помощью суффиксного массива за O(|s| + log|t|). Используем LCP в суфф.массиве за O(1).
2. Алгоритм цифровой сортировкой за O(nlogn)
1. Суффиксы ↔ циклические сдвиги
2. Цифровая сортировка строк за O(n(n+Σ))
3. Цифровая сортировка циклических сдвигов за O(Σ + nlog²n)
4. Версия с сортировкой подсчётом внутри за O(Σ + nlogn)
5. Делаем сортировку устойчивой (+1 проход в конце).
6. Оптимайз: Σ = n ⇒ break;
3. Алгоритм Касаи построения LCP за O(n)
1. Алгоритм для суффиксов
2. Алгоритм для циклических сдвигов
4. Алгоритм Каркайнена-Сандерса построения суффиксного массива за O(n)