匹配

题目限制

1000 ms 512 M

题目描述

有一个通配串 $t$，由小写字母及两种字符 '.' 和 '*' 构成。其中 '.' 可以匹配任意一个字符，'*' 可以将它的前一个字符复制 $0\sim$任意多次。

现在给出一个仅包含小写字母的字符串 $s$，请你求出有多少个 $s$ 的非空前缀可以匹配 $t$？

输入格式

本题包含多组测试数据。第一行输入一个正整数T，表示数据组数。 之后对于每组数据，第一行输入一个字符串s，第二行输入一个字符串t。 其中1≤|s|,|t|≤2000，T≤5。

输出格式

对于每组数据，输出一行一个数表示答案。

数据范围

对于20%的数据，$1 \le |s|,|t|\le 10$；

对于40%的数据，$1 \le |s|,|t|\le 100$；

另有20%的数据，保证 $t$ 中不含 '.'；

对于100%的数据，$1 \le |s|,|t|\le 2000, 1\le T\le 5$，保证 $s$ 中仅含小写字母，$t$ 中仅含小写字母和 '.''*'，且 $t$ 中首字母不为 '*'。

输入样例

2
abbbb
.*
aaabbb
a*.b.*

输出样例

1
2

样例解释

对于第一组数据abbbb，

'.' 表示a，但由于后续字符中没有a，所以 '*' 只能表示0个a，因此能匹配的前缀只有a。

对于第二组数据aaabbb，

若第一个 '*' 表示两个a，则两个 '.' 都表示b，第二个 '*' 只能表示0个b；

若第一个 '*' 表示一个a，则第一个 '.' 表示a，第二个 '.' 表示b，第二个 '*' 可以表示0个或1个b；

其它情况均无法匹配。能匹配的前缀有aaabb,aaabbb。