C1250 [JSOI2013]编程作业

内存限制:256 MB 时间限制:1000 ms

题目描述

考虑到如下的两段代码,很容易发现他们其实是一样的。

代码 1

int i, j;
i = 3;
j = i + 1;

代码 2

int a, i;
a = 3;
i = a + 1;

这是因为这两段代码之间唯一的差异,只是他们更换了一下变量名,比如第一段代码中的 $i$ 变成了第二段的 $a$,第一段的 $j$ 变成了第二段的 $i$。而其他的常量,例如 $3$,$1$ 或者其他的关键字和运算符,比如int+;。都是没有发生变化的。

不过注意到如下的代码片段,我们并不能简单认为这是一样的,因为这不是一个简单的替换,而是可以导致不同运算结果的。

代码 3

a = 3;
b = 3;

代码 4

c = 3;
c = 3;

为了简化问题,我们用大写字母来表示所有的关键字、常量等非变量符合。

假如我们采用如下的替换表

$\begin{array}{|c|c|c|c|c|c|c|c|} \hline 符号 & \texttt{int} & \texttt{,} & \texttt{;} & \texttt{=} & \texttt{3} & \texttt{+} & \texttt{L} \\ \hline 字母 & \texttt{A} & \texttt{B} & \texttt{C} & \texttt{D} & \texttt{E} & \texttt{F} & \texttt{G} \\ \hline \end{array}$

那么最开始给出的两段雷同代码就可以分别写成AiBjCiDECjDiFGC以及AaBiCaDECiDaFGC。或者简单的说,我们认为这两段代码是一样的。

现在请写一个程序,处理若干这样的代码雷同检测问题:给一个完整代码以及一个较短的代码片段,请求出,这个代码片段在完整代码中一共出现了多少次。(代码片段出现的位置可以重叠)。

为了简单起见,我们认为程序中只会至多出现 $a \sim z$ 这 $26$ 个变量,同时也至多只有 $A \sim Z$ 这 $26$ 个非变量符号。

输入格式

第一行包含一个整数 $Q$ 表示此数据中一共包含 $Q$ 个询问。

接下来 $2Q$ 行,每两行为一个询问。

每个询问中的第一行包含一个字符串 $S$,表示完整代码,第二行包含一个字符串 $T$,表示需要检测出现次数的代码片段。

输出

一共输出 $Q$ 行,每行一个整数,表示对应代码片段的出现次数。

样例

样例输入 1

3 AiBjCiDECjDiFGC AaBiCaDECiDaFGC cDEcDEbDE aDEbDE ccddef aab

样例输出 1

1 1 2

提示

$Q \le 3,|T| \le 100000,|S| \le 1000000$