Just Another String Matching Problem

Given a text string T and a pattern P, your task is to count the number of nonempty substrings of T that matches P.
Note that we're counting occurrences, so text 'aa' have two substrings that matches 'a', even though they're the same.
Formally, a text T is a non-empty string of lowercase letters, a pattern P is a non-empty string of lowercase letters, question marks (?) and asterisks (*). A question mark matches exact one letter, an asterisk matches zero or more letters.

The first line contains a single integer T (T <= 50), the number of test cases.
Each case contains exactly two non-empty lines. The first line is the text, T, the second line is the pattern P. T will only contain lowercase letters while P will only contain
lowercase letters, question marks and asterisks. Neither of them can have more than 3000 characters.

For each test case, print the case number and the number of substrings of T that matches P.

3
aa
a
abb
?b
aab
*b*

Case 1: 2
Case 2: 2
Case 3: 3

2009 Asia Regional Ningbo Online