eolymp
bolt
Try our new interface for solving problems
Məsələlər

Период

Период

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Для каждого префикса заданной строки S состоящей из N символов (каждый символ имеет ASCII-код от 97 до 126 включительно), мы хотим знать, является ли префикс периодической строкой. То есть, для каждого i (2iN), мы хотим найти такое наибольшее K > 1 (если оно есть), что префикс строки S длиной i, может быть записан в виде A^K, то есть повторенная K раз, некоторая часть строки A. Конечно же, мы хотим знать, каков период K.

Giriş verilənləri

Входные данные состоят из нескольких тестов. Каждый тест состоит из двух строк. Первая содержит N (2N1000000) - размер строки S. Вторая строка содержит саму строку S. Входные данные заканчиваются строкой, содержащей ноль.

Çıxış verilənləri

Для каждого теста вывести в отдельной строке "Test case #" и порядковый номер теста, а затем, в отдельных строках для каждого префикса длины i, вывести его период, если K > 1. Выводить размер префикса i и его период K через один пробел, размеры префиксов должны идти в порядке возрастания. Между разными тестами вывести пустую строку.

Nümunə

Giriş verilənləri #1
3
aaa
12
aabaabaabaab
0
Çıxış verilənləri #1
Test case #1
2 2
3 3

Test case #2
2 2
6 2
9 3
12 4
Mənbə SEERC 2004