代码：
#include <iostream>
using namespace std;
void get_next(string s,int n,int *next){
//初始化next数组
next[0]=-1;
next[1]=0;
next[2]=1;
for(int i=3;i<n;i++){
if(s[i-1]==s[next[i-1]]){
next[i]=next[i-1]+1;
}else{
int k=next[i-1]; //初始化一下s的下标
//不相等，一直循环
while(1){
if(k==0||next[k]==-1){
next[i]=1;
break;
}else{
if(s[i-1]==s[next[k]]){
next[i]=next[k]+1;
break;
}else{
k=next[k];
}
}
}
}
}
}
int kmp(string s1,string s2,int *next){
int i=0,j=0;
int s1_len=s1.size(),s2_len=s2.size(); //要注意这里，要先把s1和s2的长度用int类型标识出来，否则会错的，这里卡的我都快崩溃了
while(i<s1_len&&j<s2_len){
if(j==-1||s1[i]==s2[j]){
i++;
j++;
}else{
j=next[j];
}
}
if(j>=s2.size()){
int pos=i-s2.size()+1;
return pos;
}else{
return 0;
}
}
int main(){
int m=3;
while(m--){
string s1,s2,s3;
cin>>s1>>s2;
int *next=new int[s2.size()+1];
s3='0'+s2;
//求next数组
get_next(s3,s3.size(),next);
// for(int i=0;i<s3.size();i++){
// cout<<next[i]<<endl;
// }
//kmp字符串匹配
int pos=kmp(s1,s2,next);
cout<<pos<<endl;
}
return 0;
}
结果：
