PERIOD  Period
For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as A^{K }, that is A concatenated K times, for some string A. Of course, we also want to know the period K.
Input
The first line of the input file will contains only the number T (1 <= T <= 10) of the test cases.
Each test case consists of two lines. The first one contains N (2 <= N <= 1 000 000) – the size of the string S. The second line contains the string S.
Output
For each test case, output “Test case #” and the consecutive test case number on a single line; then, for each prefix with length i that has a period K > 1, output the prefix size i and the period K separated by a single space; the prefix sizes must be in increasing order. Print a blank line after each test case.
Example
Input: 2 3 aaa 12 aabaabaabaab Output: Test case #1 2 2 3 3 Test case #2 2 2 6 2 9 3 12 4
hide comments
shiva:
20150512 00:30:52
Last edit: 20150512 00:53:50 

krish:
20150502 20:23:45
KMP failure function that's all you need :) Last edit: 20150502 21:05:10 

Sunil:
20150426 20:27:18
similar to findsr 

sai krishna:
20150309 14:38:58
easy and good problem enjoyed kmp:) 

aqua:
20141209 21:56:05
can anybody tell me why my code is giving run time error


Hemanth Shivasubramaniam:
20140831 23:18:19
I've tried numerous test cases, I seem to be getting the right output.


aristofanis:
20140317 18:07:40
What is the proper way to read the input? scanf gets WA, while cin get AC... 
Added by:  ThanhVy Hua 
Date:  20041226 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  ACM South Eastern European Region 2004 