例题4.7Oulipo

#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; 
}