HUST Monthly 2010.04.05
From: 2010-04-05 12:00:00
To: 2010-04-05 17:00:00
Now: 2017-09-20 01:04:48
B - Repetitions of Substrings
Time Limit: 20s
Memory Limit: 128MB
Submissions: 508 Solved: 103
- The “repetitions” of a string S(whose length is n) is a maximum number “k” such that:
1) k is a factor of n
2) S[0..n/k-1] = S[p*(n/k)..(p+1)*(n/k)-1] for all that (1 <= p < n/k)
the repetitions of “aaaaaa”is 6.
the repetitions of “abababab”is 4.
the repetitions of “abcdef”is 1.
Now, given a string S and a number K, please tell me how many substrings of S have repetitions NOT less than K.
- The input consists of several instances, each one for a single line.
S is a string, K is a number. Check the Description for their meanings.
S contains lowercase letters(ie 'a'..'z') only.
1 <= length of S <= 100000.
1 <= K <= length of S.
- For each instance, output the number of substring whose repetitions is NOT less than K.
- Sample Input
- Sample Output
- Hust Monthly 10.04.05/Rocket323