思路

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.
//  Copyright © 2020 sgxm. All rights reserved.
//

#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;
}