Description
给出两个字符串P和T（仅由大写字母构成），请你计算字符串P在T中出现的次数。
Input
第一行一个整数n，表示数据组数，每组数据包含两行，第一行是字符串P，第二行是字符串T。
Output
对于每组数据输出一个整数，表示P在T中出现的次数。
Hint
1<=|P|<=10 000|P|<={T|<=1 000 000
Solution
P是模式串，T是主串，定义i,j两个假指针，用i指向主串，用j指向模式串，普通算法是通过strlen得到两个串的长度后，遇到不匹配的地方，i,j都需要回退，时间效率为O（mn），为了提高效率，使得i不回退，只有j这个指针回退，那么就需要求得P这个模式串的最大前缀与后缀，使得当遇到不匹配的地方时j只需要回退到最大前缀的最后一个位置，而i就不需要回退，只需要继续++。实现这个过程就需要一个fail数组用来存放当每个j遇到与i不匹配时，将要回退到什么地方。
首先因为Input有多组数据，所以每一次程序开始的时候最好进行清零（ql函数）。
输入T,P两个字符串，在setfail之前用strlen得到两个串的长度，此时用k,j两个假指针指向模式串，当1这个位置不匹配时fail应该回退到0这个位置，将fail[0]初始化为-1，那么当1这个位置不匹配时就会++，此时fail[1]=0，当k与j不匹配且k>=0时，即k还可以回退的时候，每次不匹配k就进行回退直到k,j匹配，而j只需要++，并将fail[j]赋值为k，那么每次i,j不匹配时，j=fail[j]，j就会回退到最大前缀的最后一个位置。
而kmp的过程与setfail的过程非常相似，只是指向的是两个数组，i指向T，j指向P，由于问题求的是P在T中出现的次数，需要用一个cnt来记录出现的次数。每到不匹配的时候j就进行回退（回退只需要j=fail[j]就可以回退），否则i++,j++。每到j全部匹配完一次就将cnt++，然后再次把j回退到fail[j]就可以了。
注意事项：
1.输入T和P串时是从0位置开始输入的所以strlen得到的字符长度多了1，循环的时候不需要取等。
2.在将i和j进行跳动的时候i和j要同时++。
3.习惯每次输出数据打 。
4.setfail之后要把j清零。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define maxn 1000001
using namespace std;
char T[maxn],P[maxn];
int fail[maxn];
int i,j,k,m,n,u,cnt;
void ql(){
memset(T,0,sizeof(T));
memset(P,0,sizeof(P));
memset(fail,0,sizeof(fail));
i=j=m=n=cnt=0;
}
void init(){
scanf("%s",P);
scanf("%s",T);
}
void setfail(){
m=strlen(T);
n=strlen(P);
fail[0]=-1;
k=-1;j=0;
for(;j<n;){
while(P[k]!=P[j]&&k>=0){
k=fail[k];
}
k++;
j++;
fail[j]=k;
}
}
void kmp(){
j=0;
for(int i=0;i<m;){
while(P[j]!=T[i]&&j>=0){
j=fail[j];
}
i++;
j++;
if(j==n){
cnt++;
j=fail[j];
}
}
}
int main(){
scanf("%d",&u);
for(int p=1;p<=u;p++){
ql();
init();
setfail();
kmp();
printf("%d
",cnt);
}
return 0;
}