1352 - 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
© 2015 HUST ACMICPC TEAM. All Right Reserved.