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.
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 100000,
inclusive.The last test case is followed by a line containing one -1.
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.
0 aabbab ab 1 aabbab ab 2 aabba ab -1
Case 1: 1 Case 2: 3 Case 3: 4
Migrated from old NTUJ.
2009Hefei
| No. | Testdata Range | Score |
|---|