Just Another String Matching Problem

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

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.

Input

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.

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

Hint

wujianhua

Source

2009 Asia Regional Ningbo Online

提交代码