TopCoder

User's AC Ratio

93.3% (28/30)

Submission's AC Ratio

36.4% (67/184)

Tags

Description

一個k-口吃字串就是"某一個長度為k的字串重複兩次"
例如 abcdabcd 是一個 4-口吃字串
而 aaaaaaaa 也是一個 4-口吃字串(aaaa重複兩次)
abcabc, abcdeabcde, aaaaaaa 則都不是 4-口吃字串

對於一個字串 S
其中的 "k-口吃子字串" 就是一個 S 的子字串, 且他同時也是一個 k-口吃字串
子字串在這裡的定義就是 S 的連續一小部份 (也可以是全部)
比方說如果 S 是 abcdefg,
則 ab, cdef, abcdefg, g 等等都是 S 的子字串

給你一個字串 S
請回答其中有幾個 "k-口吃子字串"?

Input Format

輸入有多組測試資料!! 以EOF作為結尾。

每組測資有兩行, 第一行是一個整數 k
第二行是一個字串 S

S 的長度不超過 100,000
你可以假設 S 裡面都是英文小寫字母

Output Format

請輸出對於 S 有幾個 k-口吃子字串?

Sample Input

3
aaaaaaaa
4
abcdabcdzabcdabcdabcd
6
abcdefgabcdef
2
ababxabababyababababzab

Sample Output

3
6
0
9

Hints

Problem Source

原TIOJ1735 / kelvin

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 65536 262144