FILRTEST - File Recover Testing
In a recent programming contest appeared a problem named “File Recover”. In that
problem, repeated strings of a given text were to be counted. You are preparing test
cases for that problem, and in order to test for border cases you want to generate a text
with many repetitions of a particular string.
Of course, test cases cannot be arbitrarily long, so you decided to choose a length and a
string, and then fit in a text of that length as many repetitions as possible of the string.
For instance, if the length is 14 and the string is “abcab”, you may generate the text
“abcabcabcabcab” whose length is 14 and where the string “abcab” appears 4 times
(starting at positions 1, 4, 7 and 10).
You would like to know how good your idea is before implementing. Given a length and
a string, you must determine the maximum number of times the characters of the string
can appear consecutively in a text of that length.
Each test case is described using a single line. The line contains an integer K (1 ≤ K ≤
109 ) and a non-empty string S of at most 106 lowercase letters. The end of input is
indicated with a line containing the number −1 and an asterisk (“*”).
For each test case, output a single line with a single integer representing the maximum
number of times the characters of S can appear consecutively in a text of length K.
Nice KMP Problem. Just build the KMP pre-processing array & then just simple calculation.
Any test case ?
AC in 1 go :-)
nice one taught new Z algo
Am getting WA even thought it worked on my machine..any idea?
easy kmp !!
Pablo Ariel Heiber:
File Recover is a problem of 2009 latin american regional: http://acm.uva.es/archive/nuevoportal/region.php?r=sa&year=2009