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 AK , that is A concatenated K times, for some string A. Of course, we also want to know the period K.
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.
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.
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
Last edit: 2015-05-12 00:53:50
KMP failure function that's all you need :)Last edit: 2015-05-02 21:05:10
similar to findsr
easy and good problem enjoyed kmp:)
can anybody tell me why my code is giving run time error
I've tried numerous test cases, I seem to be getting the right output.
What is the proper way to read the input? scanf gets WA, while cin get AC...