输入

第一行一个整数N，表示测试数据组数。

接下来的N*2行，每两行表示一个测试数据。在每一个测试数据中，第一行为模式串，由不超过10^4个大写字母组成，第二行为原串，由不超过10^6个大写字母组成。

其中N<=20

输出

   对于每一个测试数据，按照它们在输入中出现的顺序输出一行Ans，表示模式串在原串中出现的次数。

样例输入 

5

HA

HAHAHA

WQN

WQN

ADA

ADADADA

BABABB

BABABABABABABABABB

DAD

ADDAADAADDAAADAAD 

样例输出  

3

1

3

1

0 

实现代码如下：

#include
     
      #include
      
       using namespace std;int sum;//用来记录出现过这样的子串的次数int GetNext(string t,int *next);void KMPmatch(string s,string t);int main(){  string s,t;//t模式串,s原串  int n;  cin>>n;  while(n--){    cin>>t>>s;    sum=0;    KMPmatch(s,t);    cout<
       
        <
       
      
     

每完整匹配一次成功后，就让j=next[j]，为什么这么做，我们通过一个例子就知道。

假设有一个原串S：CABABABDBA，模式串T：ABAB，现在来寻找模式串T在原串S中出现的次数。