KMP算法

可修改边界
来源于： https://www.bilibili.com/video/BV1TA411h7eY?t=2195

#include<iostream>
#include<vector>
#include<string>
using namespace std;
void Next_pre(string p, vector<int> &Next)
{
    for (int i = 1, j = 0; i < (int)p.size(); i++)//i是当前遍历到的后缀  j是前缀
    {
        //跳转
        while (j && p[i] != p[j])   j = Next[j - 1];
        //前后缀一样  前缀开始往后
        if (p[i] == p[j])  j++;
        Next[i] = j;
    }
}
int Kmp_match(string s, string p, int begin)
{
    vector<int>Next(p.length());
    Next_pre(p, Next);
    for (int i = begin, j = 0; i < (int)s.length(); i++)
    {
        //跳转
        while (j && s[i] != p[j])  j = Next[j - 1];
        if (s[i] == p[j])  j++;//匹配成功一个，进行下一个
        if (j == p.length())
        {
            //完全匹配成功
            return i - p.length() + 1;
        }

    }
    return -1;

}
int main()
{
    string s, p;
    cin >> s >> p;
    cout << Kmp_match(s, p, 0);

    return 0;
}