BGTSTR - Bhagat and String
Bhagat loves string very much. Bhagat is given a string S and an integer N. He hates a string P which is substring of S and occurs at least N times in S. Your task is to find maximum length of substring P of S which occurs at least N times.
If there are multiple solutions then substring with right most occurrence is preferred.
Input
First line will contain T, denoting number of test cases. Each test case consist of two lines. The first line contains the string S and the next line contains the integer N.
Output
If there is no solution, output HATE, otherwise, print two integers in a line, separated by a space. The first integer denotes the maximum length of a substring appearing at least N times; the second integer gives the rightmost possible starting position of such a substring.
Constraints
0 < T <= 10
1 <= |S| <= 50000
1 <= N <= |S|
S consists of only lowercase letters.
Sample
Input: 3 aaaaaaa 3 babab 2 abcde 3 Output: 5 3 3 3 HATE
hide comments
(Tjandra Satria Gunawan)(曾毅昆):
2015-01-14 05:39:30
be careful when N=1, it cost me 1 WA.
|
Added by: | NISHANT RAJ |
Date: | 2014-11-05 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |