# leetcode28 KMP模板

#### 思路

KMP 模板
https://www.zhihu.com/question/21923021
– 首先理解 PMT，以及根据 PMT 如何进行回溯；其与 next 不同
– next 数组指的是 pattern 当前位匹配不上时，应该回溯到哪一位继续匹配
– p[j] == t[k] 时更新 next[j+1]==k+1，思路时 j+1 匹配不上时回溯要考虑前一位的匹配情况

#### 源码

``````//
//  leetcode28.cpp
//  test
//
//  Created by sgxm on 2020/8/5.
//

#include <stdio.h>
#include <string>
#include <iostream>
#include <vector>
using namespace std;

vector<int> calNext(string p){
vector<int> next(p.length());
next[0] = -1;
int j = 0,k = -1;
while(j<p.length()-1){
if(k==-1||p[j]==p[k]){
j++;k++;
next[j]=k;
}else{
k = next[k];
}
}
return next;
}
int main(){
string p =      "ababca";
string target = "abcababca";
vector<int> next = calNext(p);
int j = 0,i = 0;
while((j<(int)p.length())&&(i<(int)target.length())){
if(j==-1||p[j]==target[i]){
i++;j++;
}else{
j = next[j];
}
//        if((j<p.length())&&(i<target.length()))
//            cout <<i<<" < "<<target.length()<<","<<j<<" < "<<p.length()<<endl;
}
// cout << j;
if(j == p.length()){
cout <<i-j<<endl;
}else{
cout <<-1<<endl;
}
return 0;
}

``````