开头准备：
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 100
int next[MAXN];
生成next数组的函数：
void getnext(string pattern){
int m = pattern.size();
int j = 0;
next[j] = -1;
int t = next[j];
while (j < m) {
if(j == -1 || pattern[j] == pattern[t]){
t++;
j++;
next[j] = t;
}else{
t = next[t]; //当不匹配的时候让子串当前下标跳转到next数组值对应下标
}
}
}
KMP函数：
int kmp(string text, string pattern){
getnext(pattern);
int n = text.size();
int m = pattern.size();
int i = 0;
int j = 0;
while (i < n && j < m){
if(j == -1 || text[i] == pattern[j]){
i++;
j++;
}else{
j = next[j]; //当不匹配的时候让子串当前下标跳转到next数组值对应下标
}
}
if( j == m){
return i - j;
}
else{
return -1;
}
}
主函数：
int main (){
string text,pattern;
cin >> text >> pattern;
int pos = kmp(text,pattern);
cout << pos << endl;
return 0;
}
