OJ现已增加邮箱找回密码功能，还没有绑定邮箱的同学们请抓紧时间，以免密码丢失无法找回


问题1213--万能串匹配

1213: 万能串匹配

时间限制: 1 Sec  内存限制: 128 MB
提交: 42  解决: 17
[提交] [状态] [讨论版] [命题人:]

题目描述

给你一个主串S和一个模式串T，模式串中含有万能字符`$`，该字符可以代替成任何字符，且每个`$`必须代替成一个字符，请问有多少个主串S的子串可以和模式串T匹配。

输入

输入t（1<=t<=10）,表示有t组样例；
接下来输入t组样例，每组样例输入两个字符串主串 S 和 模式串 T (主串S长度<=10000，模式串长度<=100)。

输出

输出t行，每行输出每组样例的可以匹配的子串数量 。

样例输入 Copy 

3
abcdafa
a$$
abcadacaf
$a$
abcdef
$

样例输出 Copy 

2
3
6

来源/分类

串 
[提交] [状态]