Aguin has two strings A with the length of n and B with the length of m only contains lowercase letters. But the strings are such antiques that some characters can’t be recognized , and it can be any lowercase letters. Now Aguin is wondering whether A is a substring ofB. However, his way of match is a little strange. The detailed rules for match are as follows : the beginning of the A is aligned with the itcharacter of the B, and every character in the A can find the same one in B, and the position deviation does not exceed the k, then it is considered that A is matched with B in the subordinate position of the B. That is to say, for all j, there is a p, which the| j |≤k, i+j≤m and A[j] = B[p] all valid. And if k=0, string ”***” can be matched with any other strings which length is 3. Given strings A, B and the number k, you are supposed to find how many locations can A be matched in B.
Aguin has two strings A with the length of n and B with the length of m only contains lowercase letters. But the strings are such antiques that some characters can’t be recognized (replaced with ’*’), and it can be any lowercase letters. Now Aguin is wondering whether A is a substring of B. However, his way of match is a little strange. The detailed rules for match are as follows : the beginning of the A is aligned with the itℎ character of the B, and every character in the A can find the same one in B, and the position deviation does not exceed the k, then it is considered that A is matched with B in the subordinate position of the B. That is to say, for all j(1 ≤ j ≤ |A|), there is a p(1 ≤ P ≤ |B|), which the | j−(p−i+1) |≤k, i+j≤m and A[j] = B[p] all valid. And if k=0, string ”***” can be matched with any other strings which length is 3. Given strings A, B and the number k, you are supposed to find how many locations can A be matched in B.
