ZOJ Problem Set - 3249
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.
InputThe 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.
OutputFor 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
Author: Tang, Wenbin
Source: The 2009 ACM-ICPC Asia Ningbo Regional Online Contest