#include <iostream>
#include <string>
using namespace std;
int main()
{
int *Next(string P);
int KMP_FindPat(string S,string P,int *N);
string S,P;
int *N;
cout<<"输入目标串S："<<endl;
cin>>S;
cout<<"输入模板串:"<<endl;
cin>>P;
cout<<"您输入的目标串为："<<endl;
cout<<S;
cout<<"您输入的目标串为:"<<endl;
cout<<P;
N=Next(P);
int c=KMP_FindPat(S,P,N);
if(c==-1) cout<<"找不到匹配的子串!"<<endl;
else cout<<"匹配成功"<<"开始位置为："<<c<<endl;
return 0;
}
int *Next(string P)
{
int m=P.size();
int *N=new int[m];
N[0]=0;
for(int i=1;i<m;i++)
{
int k=N[i-1];
while(k>0&&P[i]!=P[k])
k=N[k-1];
if(P[i]==P[k])
N[i]=k+1;
else N[i]=0;
}
return N;
}
int KMP_FindPat(string S,string P,int *N)
{
int LastIndex=S.size()-P.size();
if(LastIndex<0)
return (-1);
int i;
int j=0;
for(i=0;i<S.size();i++)
{
while(P[j]!=S[i]&&j>0)
j=N[j-1];
if(P[j]==S[i])
j++;
if(j==P.size())
return (i-j+1);
};
return(-1);
}
