字符串（hash，kmp）

题目描述:

给出两个串s1，s2（只有大写字母），求s1在s2中出现了多少次。

例如s1="ABA"，s2="ABABA"，答案为2。

输入T组数据, 每组数据两行，对每数据输出结果。

样例输入:

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

样例输出:

1
3
0

提示:

s1字符串的长度<=10⁴， s2字符串的长度<=10⁶。

时间限制: 1000ms
空间限制: 256MB

---