Нормализация: когда «равны» значит не «равны»

Часто спрашивают не «равны ли куски», а «равны ли они с точностью до чего-нибудь»: до прибавления константы, до поворота алфавита, до перестановки символов.

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

Сдвиг на константу

Даны массивы чисел. Вхождение $b$ в $a$ «со сдвигом» значит $a[l + i] = b[i] + d$ при каком-то общем $d$.

Инвариант - последовательность разностей соседей. Прибавление константы её не меняет:

$$b[i+1] - b[i] = (b[i+1] + d) - (b[i] + d)$$

Значит, надо искать разности $b$ в разностях $a$ обычной префикс-функцией.

Две ловушки, обе на границах:

Разностей на одну меньше. У массива длины $k$ их $k - 1$. При $k = 1$ разностей нет вовсе, и подходит любая позиция - этот случай надо обрабатывать отдельно, иначе решение либо упадёт, либо выведет пустоту.

Разности не влезают в тип. При $a_i \le 10^9$ разность лежит в $[-10^9, 10^9]$ и в int помещается, но если границы чуть шире - уже нет. И сравнивать разности как символы строки нельзя: это числа, нужен вариант префикс-функции по массиву int, а не по char.

Поворот алфавита

Шифр Цезаря - тот же сдвиг, только по модулю размера алфавита. Инвариант тот же: разности соседних букв по модулю 26.

Если вдобавок разрешён циклический сдвиг самой строки, разности надо брать циклически - включая пару «последняя буква, первая». Тогда у строки длины $n$ ровно $n$ разностей, и циклический сдвиг строки превращается в циклический сдвиг последовательности разностей. А это уже знакомая задача: искать $d(t)$ в $d(s) + d(s)$.

Почему именно циклические разности, а не обычные: при обычных длина падает до $n - 1$, и информация о стыке теряется - строки ab и ba стали бы неразличимы.

Восстановить сам сдвиг просто: если совпадение нашлось в позиции $k$, то первая буква результата - это $s[k]$, и поворот $d$ считается из $s[k] - d = t[0]$.

Проверено: на 40 000 парах строк длины до 7 ответ совпал с полным перебором всех пар (сдвиг, поворот) - и там, где преобразование существует, и там, где его нет.

Перестановка символов

Анаграммы - это равенство мультимножеств. Инвариантов тут два, и выбор между ними важен.

Счётчики букв. Если алфавит маленький, храните массив из 26 чисел и двигайте окно: при сдвиге на единицу меняются два счётчика. Сравнение окон - $O(26)$, всего $O(26n)$. Точно и просто.

Хеш мультимножества. Если значения большие или алфавита нет вовсе, каждому значению сопоставляют случайное 64-битное число и берут сумму по окну. Сумма не зависит от порядка - это и есть коммутативный хеш. Считается префиксными суммами, окно любой длины - за константу.

Подробнее про второй способ - «Хеширование множеств».

Осторожно с соблазном взять вместо случайных чисел сами значения: сумма значений совпадает у $\{1, 4\}$ и $\{2, 3\}$, и такое ломается на первом же тесте. Сумма квадратов ломается чуть позже, но тоже ломается.

Таблица

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

Общее правило: сначала нормализуйте, потом ищите. Попытка «учесть преобразование прямо в алгоритме поиска» почти всегда даёт лишний множитель и лишние ошибки на границах.