Строки, базовые алгоритмы (9 марта 2015)

1. Определение Z функции
2. LCP за O(n²)
3. Задачи на префикс-функцию и Z-функцию, LCP
1. Найти наибольшую общую подстроку за O(n²) (3 решения: префикс, Z, LCP)
2. Найти подстроку в тексте с возможностью одной опечатки за O(n) (z-функция с начала, z-функция с конца)
3. Найти все периоды строки Z-функцией
4. Найти все периоды строки Prefix-функцией (лемма: если +i, +j, то +gcd(i,j))
5. Для каждого префикса строки S проверить его периодичность
6. Найти в тексте s слово a, за ним слово b так, чтобы расстояние между вхождениями было минимально
7. Найти номер строки в её суффиксном массиве
4. Задачи на хеши
1. Общая идея #1: любые две строки можно сравнить на равенство за O(1)
2. Общая идея #2: любые две строки можно сравнить на больше/меньше за O(logn) бинпоиском
3. Суф.массив за O(nlog²n)
4. Z-функция за O(nlogn) хешами
5. Найти все периоды строки хешами
6. Количество различных подстрок за [O(n²), O(n)]
7. Самая длинная общая подстрока за [O(nlogn), O(n)]
8. Найти максимальную по длине строку, которая входит строку S два раза без наложения [O(nlogn), O(n)]
9. Количество подпалиндромов строки за O(nlogn)
10. Самый длинный подпалиндром за O(n)