АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

176. Сообщение

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Некой научно-исследовательской лаборатории, занимающейся поиском внеземных цивилизаций, наконец-то удалось настроить свой радиотелескоп на приём сигнала явно искусственного происхождения. Сигнал очевидным образом представляется в виде последовательности битов, и аппаратуру настроили так, чтобы он записывался на жёсткий диск в виде текста из символов 0 и 1.

Через некоторое время у исследователей появилось подозрение, что передача циклически повторяется, т.е. по окончании передачи сообщение сразу же начинает передаваться повторно, и оно уже несколько раз целиком принято и сохранено на диске (заметим, что в начале и конце строки сообщение может быть оборвано).

Чтобы проверить это, программистам (то есть вам) предложено решить следующую задачу. Дана текстовая строка t, содержащая символы 0 и 1. Найти минимально возможную длину такой её подстроки w, что t можно представить в виде swww...wp, где s - суффикс строки w (т.е. её конец), p - префикс строки w (т.е. её начало). Строки s и p могут быть пустыми, а w должна повторяться хотя бы 2 раза.

Входные данные содержат принятый сигнал - строку t из символов 0 и 1, длина t не превышает 1 000 000 символов.

Выходные данные должны содержать единственное число - минимально возможную длину сообщения w. Если t нельзя представить в указанном виде, выведите ноль.

Пример

Входные данные
Результат

0010110010110010110010

6

Пояснение к примеру

Одним из возможных вариантов будет сообщение 011001, принятое следующим образом: 001 011001 011001 011001 0.

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / IX Межвузовская олимпиада 2006 /
175. E - Марсоход 176. 177. G - Скобки 178. H - Транслятор
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, смена 2019 / Строки /
568. 07 - Спутник 176. 1991. 09 - Подпалиндромы
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, сентябрь 2020 / Импульс-2020, олимпиада закрытия, группа 1 /
1434. 07 - Контроль скорости 176. 1228. 09 - Наилучший путь 296. 10 - Палиндром 1991. 11 - Подпалиндромы
 
время генерации 0.343 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.