Период строки

Строка $s$ имеет период $d$, если она получается повторением своего префикса длины $d$ — возможно, с обрывом на середине последнего повторения.

Например, у aabaabaab период 3, а у aabaabaa — тоже 3, просто последнее повторение неполное.

Ищем наименьший период. Тривиальный ответ $d = n$ есть всегда: строка — повторение себя один раз.

Случай полного повторения

Сначала более простая постановка: строка обязана разбиваться на целое число копий.

Тогда $d$ — делитель $n$, и достаточно перебрать делители. Для каждого проверяем, что все блоки длины $d$ одинаковы:

for (int d = 1; d <= n; d++) {
    if (n % d != 0) continue;
    bool ok = true;
    for (int i = d; i < n && ok; i += d)
        if (h.get(0, d) != h.get(i, i + d)) ok = false;
    if (ok) { /* нашли период d */ break; }
}

Для делителя $d$ работы $\frac{n}{d}$, суммарно $\frac{n}{1} + \frac{n}{2} + \dots = O(n \log n)$ — гармонический ряд.

Общий случай: трюк со сдвигом

Когда последнее повторение может быть неполным, делители не помогают: период — любое число от 1 до $n$.

Здесь работает красивый критерий:

$d$ — период строки $s$ длины $n$ тогда и только тогда, когда $s[0, n-d) = s[d, n)$.

То есть строка совпадает сама с собой, сдвинутая на $d$.

for (int d = 1; d <= n; d++)
    if (h.get(0, n - d) == h.get(d, n)) return d;

Одно сравнение хешей на каждое $d$, итого $O(n)$ после предподсчёта.

Проверено: на ста тысячах случайных строк результат совпал с посимвольной проверкой.

Почему критерий верен

В одну сторону очевидно: если $s$ — повторение блока длины $d$, то сдвиг на $d$ совмещает блоки друг с другом.

В другую сторону интереснее. Пусть $s[0, n-d) = s[d, n)$. Это равенство означает, что $s_i = s_{i+d}$ для всех допустимых $i$.

Возьмём любую позицию $i$. Применяя равенство многократно, получаем $s_i = s_{i+d} = s_{i+2d} = \dots$ — то есть все позиции с одинаковым остатком по модулю $d$ несут один и тот же символ.

А это в точности и значит, что строка состоит из повторений блока длины $d$.

Ключ в том, что одно равенство длинных кусков сразу даёт цепочку равенств отдельных символов. Именно поэтому хватает одного сравнения вместо $\frac{n}{d}$.

Связь с префикс-функцией

Ту же задачу решает алгоритм Кнута — Морриса — Пратта: наименьший период равен $n - \pi_{n-1}$, где $\pi$ — префикс-функция.

Это точный алгоритм за $O(n)$, без вероятностей. Если вы помните КМП, берите его.

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

Родственные задачи

Является ли строка степенью другой. Проверяем, что наименьший период делит $n$.

Наибольшее $k$, что $s = t^k$. Это $n / d$ для наименьшего периода-делителя.

Период каждого префикса. Тот же цикл, но для каждого префикса отдельно — $O(n^2)$ на хешах против $O(n)$ на префикс-функции. Здесь КМП явно лучше.

Наименьший циклический сдвиг. Другая задача, хотя звучит похоже; решается сравнением подстрок удвоенной строки.