Некой научно-исследовательской
лаборатории, занимающейся поиском внеземных цивилизаций, наконец-то удалось
настроить свой радиотелескоп на приём сигнала явно искусственного
происхождения. Сигнал очевидным образом представляется в виде
последовательности битов, и аппаратуру настроили так, чтобы он записывался на
жёсткий диск в виде текста из символов 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 нельзя представить в указанном виде, выведите ноль.
Пример
|
STDIN
|
STDOUT
|
|
0010110010110010110010
|
6
|
Пояснение к примеру
Одним из возможных вариантов
будет сообщение 011001, принятое следующим образом: 001 011001 011001 011001
0.
