思路
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;
}