Задачи на строки: какой приём когда

В разделе набралось четыре независимых инструмента: префикс-функция, z-функция, автомат и бор. Плюс хеши из соседнего раздела.

Они пересекаются, но не заменяют друг друга.

Таблица выбора

задача	чем решать
найти все вхождения одного шаблона	префикс-функция или хеши
то же, но текст в потоке и не влезает в память	префикс-функция
то же, но нужен точный ответ без вероятности	префикс-функция или z-функция
наименьший период, все периоды	префикс-функция
совпадение суффиксов с началом строки	z-функция
считать строки без вхождения шаблона	автомат
много запросов «дописать символ / откатить»	автомат
хранить набор строк, запросы по префиксам	бор
лексикографические запросы к набору строк	бор
сравнить два произвольных куска текста	хеши
наибольший общий префикс двух суффиксов	z-функция или хеши с бинпоиском

Почему хеши не вытесняют остальное

Хеши короче и универсальнее: сравнить любые два куска за константу — это очень много.

Но у них три ограничения, и каждое где-нибудь да стреляет:

Вероятность. Ответ может быть неверным. На олимпиаде с открытыми тестами это ломают целенаправленно.

Нужен весь текст. Префиксные хеши считаются по массиву; в потоке их не построить.

Не дают структуры. Хеш отвечает «равны или нет». Он не скажет, чему равен период, и по нему не построить автомат для динамики.

Обратное тоже верно: там, где нужно сравнивать произвольные куски произвольных строк, префикс-функция бесполезна, а хеши решают задачу в две строки.

Типовые постановки

Строка — циклический сдвиг другой. Ищем $a$ в $b + b$ префикс-функцией.

Наименьшее дополнение до палиндрома. К строке $s$ надо приписать минимум символов справа, чтобы получился палиндром. Считаем префикс-функцию склейки $s^R \# s$; последнее значение — длина наибольшего палиндромного суффикса, остаток дописываем зеркально.

Сколько раз каждый префикс встречается в строке. Обратный проход по $\pi$: cnt[pi[i]-1] += cnt[i], справа налево.

Сжать строку до наименьшего повторяющегося блока. Период $n - \pi[n-1]$; если $n$ на него делится — это ответ, иначе строка не сжимается нацело.

Максимальный xor пары чисел в наборе. Бор на двоичных записях: кладём числа, для каждого спускаемся, стараясь на каждом бите свернуть в противоположную сторону.

Количество строк длины $L$ без вхождения шаблона. Динамика по состояниям автомата.

Автодополнение: все строки набора с данным префиксом. Спуск по бору до конца префикса, дальше обход поддерева.

Чего в разделе нет

Тема на этом не заканчивается. За её пределами остались суффиксный массив, суффиксное дерево, автомат Ахо — Корасик для набора шаблонов и алгоритм Манакера для палиндромов. Все они строятся поверх того, что здесь есть: Ахо — Корасик — это автомат на боре, а суффиксный массив тесно связан с хешами и бинарным поиском.