
ZOJ Problem Set  3249
Task 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 nonempty string of lowercase letters, a pattern P is a nonempty string of lowercase letters, question marks (?) and asterisks (*). A question mark matches exact one letter, an asterisk matches zero or more letters. Input The first line contains a single integer T (T <= 50), the number of test cases. Each case contains exactly two nonempty 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.Output For each test case, print the case number and the number of substrings of T that matches P.Sample Input 3 aa a abb ?b aab *b* Sample Output Case 1: 2 Case 2: 2 Case 3: 3 Author: Tang, Wenbin Source: The 2009 ACMICPC Asia Ningbo Regional Online Contest 