PJ的女朋友是一个书法家，喜欢写一些好看的英文书法。有一天PJ拿到了她写的纸条，暗示要送给他生日礼物。PJ想知道自己想要的礼物是不是就是她送的，于是想看看自己想要的在纸条中出现了多少次。
Input
第一行输入一个整数代表数据的组数
- 每组数据第一行一个字符串 W代表PJ想要的礼物, 包含英语字符 {'A', 'B', 'C', …, 'Z'}, 并且字符串长度满足 1 ≤ |W| ≤ 10,000 (|W| 代表 W字符串的长度).
- 接下来一行一个字符串 T代表女朋友的纸条, 也包含英语字符 {'A', 'B', 'C', …, 'Z'}, 满足 |W| ≤ |T| ≤ 1,000,000.
Output
输出一行一个整数代表 W 在 T中出现的次数.
Sample Input
3 BAPC BAPC AZA AZAZAZA VERDI AVERDXIVYERDIAN
Sample Output
1 3 0
思路：此题就是模板题，直接套模板就过了
#include <iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=1000010;
char str[maxn],pat[maxn];//pat为模式串，str为主串
int Next[maxn]; //Next[x]下标x表示匹配失败处字符下标
//模式串pat的前缀与x位置的后缀的最大匹配字符个数-1
void GetNext(char *pat)
{
int LenPat = strlen(pat);
int i = 0,j = -1;
Next[0] = -1;
while(i < LenPat)
{
if(j == -1 || pat[i] == pat[j])
{
i++,j++;
Next[i] = j;
}
else
j = Next[j];
}
}
int KMP()//返回模式串pat在str中第一次出现的位置
{
int LenStr = strlen(str);
int LenPat = strlen(pat);
GetNext(pat);
int i = 0,j = 0;
int ans = 0;//计算模式串在主串匹配次数
while(i < LenStr)
{
if(j == -1 || str[i] == pat[j])
i++,j++;
else
j = Next[j];
if(j == LenPat)
{
ans++;// ans存放匹配次数，去掉return,最后返回ans
//return i - LenPat + 1;
}
}
//return -1;//没找到匹配位置
return ans;//返回匹配次数。
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s%s",pat,str);
int i=KMP();
printf("%d
",i);
}
}