Всем привет Пытаюсь решить следующую задачу: https://informatics.msk.ru/mod/statements/view.php?id=6992&chapterid=101#1 Строка S была записана много

раз подряд, после чего из получившейся строки взяли подстроку и дали вам. Ваша задача определить минимально возможную длину исходной строки S.

Входные данные
На вход программы поступает строка, которая содержит только латинские буквы, длина строки не превышает 100000 символов.

Выходные данные
Требуется вывести одно число – ответ на вопрос задачи.
Попробовал решить через полиномиальные хэши:
1) Посчитал хэши по префиксам
2) В цикле беру префиксы и суффиксы, сравниваю их за O(1)
Код задачи: https://paste.ofcode.org/tqvtRWT4CUUrMwDduFhr5B
Но кажется в коде какой-то логический косяк, хотя он в принципе проходил похожу задачу на литкоде: https://leetcode.com/submissions/detail/1102264111/

Не подскажите в чем тут может быть косяк?

как минимум ошибка в предположении, что длина S должна делить длину строки на входе

например abca

Вот тут не могу согласиться. https://paste.ofcode.org/5GFZTbJ39D3kwx4xvVixKh size_t solve(const string &s) { vector<uint64_t> p_pow(s.length()), hashes(s.length()); compute_hashes(s, p_pow, hashes); size_t cycle_len = s.length(); for (size_t k = 1; k < s.length(); ++k) { if (substring_eq(p_pow, hashes, 0, k, s.length() - k)) { cycle_len = k; break; } } return cycle_len; } В итоге нашел более правильную версию генерации хешей

так в этом решении и нет проверки "if (n % i == 0)"

А, ты про это условие. Забыл его убрать из пасты, без него запускал

А это не про fft задача?

про кмп

Ну, я бы решал через fft для каждого символа...

как сделать из решения в 10 строчек - решение в 300 (и упавшее по TL)

Из этих 300 250 копипастятся