KMP水题
Time Limit: 1000 MSMemory Limit: 10000 KB

Description

给定文本串s与模式串t,求s中有多少个子串与t相同,两个子串视为不同仅当他们长度不等或起始位置不同。

Input

第一行输入T(T<=100)表示有T组数据。每组数据先输入两个正整数n、m(1<=n<=100000,1<=m<=n),分别表示文本串与模式串长度。紧接着输入两行字符串,即为s、t。

Output

输出T行正整数,第i行表示第i组文本串中有多少个子串与模式串相同。

Sample Input

2
5 3
ababa
aba
3 1
aaa
a

Sample Output

2
3
Submit Your Code                        Discuss



苏ICP备2022026913号-1