Алгоритмы на строках (СПБГУ МатМех, март 2013, спецкурс 344-й группы)

1. Общие факты
1. Сортировка строк стандартной функцией sort работает за O(SumLen * log)
2. Решение задач на тему прошлой лекции
1. Нахождение min циклического сдвига строки за O(n)
2. Количество подпалиндромов строки за O(nlogn)
3. Самый длинный подпалиндром за O(nlogn) и O(n)
4. Поиск подстроки в строке и подматрицы в матрице хэшами
3. Хэши
1. Наибольшая общая подстрока хэшами с бинпоиском за O(nlogn)
2. Сравнение строк на больше-меньше за O(logn)
3. Сортировка циклических сдвигов за O(nlog²n)
4. Сортировка суффиксов
5. Нахождение периода строки и периода матрицы хэшами
6. Построение LCP любых двух строк за O(logn) хэшами
7. Построение LCP всех пар за O(n²)
8. Количество подстрок строки суффиксным массивом с LCP за O(n)
9. Наибольшая общая подстрока суффиксным массивом за O(n)
4. Бор и сжатый бор
1. Алгоритм поиска словарного слова в тексте за O(|text|*max|word|)
2. Хранение бора: массив, список, set, hash-таблица, полу-массив.
3. Суффиксное дерево. Построение за квадрат.
4. Использование суффиксного дерева: поиск строки в тексте за O(|s|) (строим суф.дерево от текста)
5. Сжатый бор. Суффиксное дерево теперь использует O(n) памяти, строится за O(n²).
6. Построение суф.дерева по суф.массиву с LCP за O(n).
5. Суффиксный массив за O(nlogn)
1. Общая идея: удвоение отсортированных частей
2. Храним две вещи: порядок частей длины k и для каждой части -- её цвет
3. Переход = сортировка подсчетом пар <цвет первой половины, цвет второй половины>
4. Собственно сортировка подсчетом и цифровая сортировка за O(n)
6. Бонус
1. Использование произведения многочленов для поиска подкартинки в картинке