Задача E. Кусок ленты.
Задачу добавил: DK
Успешно сдано решений: 4
Вася работает в секретном НИИ улучшенных методик шифрования и передачи сообщений. Он должен зашифровать и передать улучшенным способом сообщение, требующее шифровки и передачи улучшенным способом, с помощью аппарата для улучшенной шифровки и передачи сообщений, требующих улучшенной шифровки и передачи. На вход аппарата должна подаваться специальная лента, содержащая сообщение длиной ровно в N символов (N - фиксированная для аппарата величина), после чего аппарат прокручивает ленту, считывая по одному символу. Вася обратил внимание, что если аппарату подать ленту длиннее N символов, аппарат все равно прочитывает ровно N символов, что натолкнуло его на следующую мысль. Он решил написать на ленте только часть сообщения, а потом склеить ленту таким образом, чтобы после подачи последнего символа в аппарат снова попадал первый символ ленты (т.е. "закольцевать" ленту). Если при этом аппарат прочитает нужную последовательность символов, будет сохранена часть дорогостоящей ленты для сообщений, требующих улучшенной шифровки и передачи. Ваша задача - помочь ему определить, какую минимальную длину может иметь новая "закольцованная" лента.
Входной файл.
Первая (и единственная) строка содержит исходное сообщение длиной N символов (2 <= N <= 500000). В целях обеспечения секретности Вася применил к символам еще один алгоритм улучшенного шифрования, и теперь в исходном сообщении присутствуют только латинские буквы и цифры.
Выходной файл.
Единственное число М, минимальная длина "закольцованной" ленты
Пример 1.
input.txt:
abababababab
output.txt:
2
Пример 2.
input.txt:
abaab
output.txt:
3
Пример 3.
input.txt:
abcdefg
output.txt:
7
Пояснение:
На новой ленте будут присутствовать первые M символов, содержащиеся на исходной ленте.