Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Задача 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 символов, содержащиеся на исходной ленте.

Сдать задачу

Задать вопрос жюри по этой задаче