概念

最长公共前后缀

前缀：不包含最后一个字符的第一个字符开头的连续子串

后缀：不包含第一个字符的以最后一个字符结尾的连续子串

Next 数组指的就是最长的公共前后缀，每当未匹配成功时，不需要全部退回，因此只是后缀不匹配，因此退到前缀继续比较，省去了冗余的比较

//
// Created by Administrator on 2021/10/20.
//

#include<iostream>
#include<string>
#include<vector>

using namespace std;

vector<int> getNext(string P){
    vector<int> next((int)P.size(), 0);
    int j = 0, k = -1;
    next[j] = k;

    while(j < (int)P.size() - 1){
        if(k == -1 || P[k] == P[j]){
            next[++j] = ++k;
        }else{
            k = next[k];
        }
    }
    return next;
}

int KMP(string S, string P){
    if(P.empty()) return 0;
    auto next = getNext(P);
    int i = 0, j = 0;
    while(i < (int)S.size() && j < (int)P.size()){
        if(j == -1 || S[i] == P[j]){
            i++;
            j++;
        }else{
            j = next[j];
        }
    }
    if(j == P.size()) return i-j;
    else return -1;
}

int main(){
    string S = "aaaaa";
    string P = "bba";
    cout<<KMP(S, P);
    return 0;
}