人情世故（一）

#include <iostream>#include <cstring>using namespace std;int nextt[500000];string nn,mm;void GetNext(int m){int i,j;nextt[0]=-1;i=-1;j=0;    while(j<m)if(i==-1||mm[i]==mm[j]){i++;j++;nextt[j]=i;}else{i=nextt[i];}}int KMP(int m,int n){GetNext(m);int i=0;//代表文本串 int j=0;//代表模式串 int count=0;//文本串中模式串的个数 while(i<n){if(nn[i]==mm[j]||j==-1){j++;i++;}else{j=nextt[j];//这一句异曲同工 }if(j==m)//一个模式串匹配成功 {count++;            j=nextt[j];//这一句异曲同工 }}return count;}int main(){int num;cin>>num;int n,m;for(int i=1;i<=num;i++){cin>>mm>>nn;m=mm.size();n=nn.size();cout<<KMP(m,n)<<endl;}return 0; }