1352 - Repetitions of Substrings

Time Limit: 20s Memory Limit: 128MB

Submissions: 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