KMP 算法 复习
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
char a[2000000],b[2000000];
int Next[2000000];
void get_next(){
Next[0] = 0;
int len = strlen(b);
int j = 0;
for(int i=1;i<len;i++){
j = Next[i-1]; //重点
while(j>0&&b[i]!=b[j])j = Next[j-1];
if(b[i]==b[j])Next[i] = j+1; //重点
else Next[i] = 0;
}
}
int kmp(){
// Next[0] = -1;
int len1 = strlen(a);
int len2 = strlen(b);
int j = 0;
for(int i=0;i<len1;i++){
while(j>0&&a[i]!=b[j])j = Next[j-1];
if(a[i]==b[j]){
// i++; //重点
j++;
}
if(j==len2){
return i-len2+1;
}
}
return -1;
}
int main()
{
while(cin>>a){
cin>>b;
get_next();
int ans = kmp();
if(ans==-1){
cout<<ans<<endl;
}
else {
cout<<ans+1<<endl;
}
}
return 0;
}
