#include<iostream>
#include<vector>
#include<string>
using namespace std;
// 处理模式串，每一个位置都赋值为已匹配的位数
vector<int> next_pos(string pattern){
//初始化next
vector<int> next(pattern.size());
next[0] = -1; // 第0个位置永远是没有用, 第一种情况，j = 0;
int k = 0;
for(int j = 1;j < pattern.size();j++){
if(pattern[k] == pattern[j-1]){
if(k == j-1){
k = 0;
next[j] = 0;
}else{
next[j] = next[j-1] + 1;
k++;
}
}else if(k!=0) {
k=0;
if(pattern[k] == pattern[j-1]){
next[j] = 1;
k++;
}else{
next[j] = 0;
}
}
}
return next;
}
bool kmp(string s, string pattern,int pos){
vector<int> next = next_pos(pattern);
int j = 0;
for(int i = 0;i < s.size() && j<pattern.size();){
if(s[i] == pattern[j]) {i++;j++;}
else{
if(j == 0) i++;
else{
j=next[j];
}
}
}
if(j == pattern.size()) return true;
return false;
}
int main() {
std::cout << "Hes "<< kmp("Hello World!","Hes",0) << " Hello World!\n";
}