D. Наименьший период

Периодом строки $s$ длины $n$ называется такое число $d$, что $s_i = s_{i+d}$ для всех $i$ от 1 до $n - d$.

Найдите наименьший период. Делимость $n$ на $d$ не требуется.

Ответ — это ровно $n$ минус наибольший бордер: одна строчка после подсчёта префикс-функции.

Стоит убедиться, что вы понимаете разницу с классной задачей про период. Там нужно было наибольшее $k$ с $s = t^k$, и делимость была обязательна. Здесь ограничения нет, и у строки aabaa ответ 3, хотя $5$ на $3$ не делится.

Одна строка длины $n$ ($1 \le n \le 10^6$) из строчных латинских букв.

Одно число — длина наименьшего периода.