| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1129
K-neighbor substrings
Time Limit: 10000ms
Memory Limit: 65536kb Description
The Hamming distance between two strings of the same length is defined as the number of positions at which the corresponding characters are different. For example, the Hamming distance between "abbab" and "bbabb" is 3.A string is called a K-neighbor of another string if and only if they are of the same length and the Hamming distance between them is not larger than K. In this problem, given an integer K and two strings A and B which only contain character 'a' and 'b', you are to count how many different sub-strings of A are K-neighbors of B. Input
The input consists of multiple test cases. Each test case starts with a line containing one integer K(0<=K<=100,000). The following two lines give two non-empty strings consisting of 'a' and 'b', which are string A and string B, respectively. The length of strings A and B will both lie between 1 and 100,000, inclusive.The last test case is followed by a line containing one -1.
Output
For each test case, print a line containing the test case number( beginning with 1) followed by the number of different sub-strings of string A which are K-neighbors of string B.
Sample Input
0 aabbab ab 1 aabbab ab 2 aabba ab -1 Sample Output
Case 1: 1 Case 2: 3 Case 3: 4 |