|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Игорь Андрианов, ВоГТУ.
Сложность Гамма
Некой научно-исследовательской лаборатории, занимающейся поиском внеземных
цивилизаций, наконец-то удалось настроить свой радиотелескоп на приём
сигнала явно искусственного происхождения. Сигнал очевидным образом
представляется в виде последовательности битов, и аппаратуру настроили так,
чтобы он записывался на жёсткий диск в виде текста из символов 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.
Для отправки решений необходимо выполнить вход.
|