Repetitions of Substrings
Time Limit : 20 Second
Memory Limit : 128 MB
Submission: 508
Solved: 103
- Description
- 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)
for example:
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.
- Input
- The input consists of several instances, each one for a single line.
S K
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.
- Output
- For each instance, output the number of substring whose repetitions is NOT less than K.
- sample input
-
abcabc 2 acmac 3
- sample output
-
1 0
- hint
- source
- Hust Monthly 10.04.05/Rocket323