Строки. Поиск подстрок

LCP для всех пар за \(O(n^2)\)
Задачи на хеши
- Общая идея #1: любые две строки можно сравнить на равенство за \(O(1)\)
- Общая идея #2: любые две строки можно сравнить на больше/меньше за \(O(\log n)\) бинпоиском
- Суф.массив за \(O(n\log^2 n)\)
- Z-функция за O(nlogn) хешами
- Найти все периоды строки хешами
- Количество различных подстрок за [O(n2), O(n)]
- Самая длинная общая подстрока, содержащая не более K пробелов за [O(nlogn), O(n)]
- Найти максимальную по длине строку, которая входит строку S два раза без наложения [O(nlogn), O(n)]
Задачи на префикс-функцию и Z-функцию, LCP
- Найти наибольшую общую подстроку за O(n2) (3 решения: префикс, Z, LCP)
- Найти подстроку в тексте с возможностью одной опечатки за O(n) (z-функция с начала, z-функция с конца)
- Найти все периоды строки Z-функцией
- Найти все периоды строки Prefix-функцией