[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
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.1ms with 1 query(s).