682 . L-Gap Substrings
Description
If a string is in the form UVU, where U
is not empty, and V has exactly L characters, we say UVU
is an L-Gap string. For example, abcbabc is a 1-Gap
string. xyxyxyxyxy is both a 2-Gap string and also a 6-Gap
string, but not a 10-Gap string (because U is non-empty).
Given a string s, and a positive
integer g, you are to find the number of g-Gap substrings in s.
s contains lower-case letters only, and has at most 50,000
characters.
Input Format
The
first line contains a single integer t, the number of
test cases. Each of the t followings contains an integer g followed by a string s.
The size of the input file is less than 1MB.
Output Format
For each test case, print the
case number and the number of g-Gap
substrings. Look at the output for sample input for details.
Sample Input 1
2 1 bbaabaaaaa 5 abxxxxxab
Sample Output 1
Case 1: 7 Case 2: 1
Hints
被雷到可能會影響您的身心健康，ACM2009培訓班關心您。(按我繼續)
Problem Source
Migrated from old NTUJ.
UVa 10829
Subtasks
| No. | Testdata Range | Score |
|---|