Фрагменты-повторы

Сложная

Назовём строку *повтором*, если она состоит из двух одинаковых половин, то есть равна w + w для некоторой непустой строки w. Например, "tictic" и "aa" — повторы, а "tic" и "abba" — нет. Дана строка text. Посчитайте, сколько **различных** её подстрок (непрерывных фрагментов) являются повторами. Одинаковые подстроки, найденные в разных местах, считаются один раз.

Пример 1

text="xyxyxy" → 2

Подходят "xyxy" и "yxyx". Фрагмент "xyxy" встречается дважды, но считается один раз.

Пример 2

text="moon" → 1

Подходит только "oo" = "o" + "o".

Пример 3

text="abc" → 0

Ограничения

1 ≤ len(text) ≤ 2000
text состоит из строчных латинских букв

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Trie String Hash Function Rolling Hash

Вход

text="xyxyxy"

Ожидается

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 99 тестов на сервере, включая скрытые.