Как через префикс-функцию найти наименьший период строки и проверить, что строка — повтор?
Дана строка длины n. Нужно понять, является ли она k-кратным повторением какого-то блока, и если да — найти минимальную длину этого блока. Слышал, что это делается через префикс-функцию в одну строку, но не понимаю формулу n - p[n-1].
2 ответа
Пусть p — префикс-функция, k = n - p[n-1]. Это длина кандидата на наименьший период. Утверждение: строка имеет период k, и если n % k == 0, то s — это ровно n/k повторений блока длины k.
Интуиция: p[n-1] — длина наибольшего собственного бордера (префикс = суффикс). Если префикс длины p[n-1] совпадает с суффиксом, то сдвиг на n - p[n-1] совмещает строку саму с собой — это и есть определение периода.
int smallest_period(const string& s) {
int n = s.size();
vector<int> p = prefix_function(s);
int k = n - p[n - 1];
return k; // наименьший период (может не делить n)
}
bool is_repetition(const string& s) {
int n = s.size();
int k = smallest_period(s);
return k < n && n % k == 0; // строка = (n/k) копий блока длины k
}
Сложность — O(n) (вся работа в префикс-функции). Важно: k всегда период, но он делит n не всегда; для «строка является целым повтором» нужна именно проверка n % k == 0.
Тонкость на контесте: если k == n (то есть p[n-1] == 0), у строки нет нетривиального периода — она «апериодична» вроде abc. Не забудьте k < n в проверке, иначе n % n == 0 даст ложное «это повтор» для любой строки. Часто на этом теряют тест.