Period#3345
For each prefix of a given string with characters (each character has an ASCII code between and , inclusive), we want to know whether the prefix is a periodic string. That is, for each (2 \leq i \leq N) we want to know the largest K > 1 (if there is one) such that the prefix of with length can be written as A^K, that is concatenated times, for some string . Of course, we also want to know the period .
The input file consists of several test cases. Each test case consists of two lines. The first one contains (2 \leq N \leq 1000000) – the size of the string . The second line contains the string . The input file ends with a line, having the number zero on it.
For each test case, output "Test case #" and the consecutive test case number on a single line; then, for each prefix with length that has a period K > 1, output the prefix size and the period separated by a single space; the prefix sizes must be in increasing order. Print a blank line after each test case.
1-nji mysal