kmp模板

我个渣渣就不在这解释什么是kmp了,列一下帮我理解kmp的视频和文章:

  1. B站up:正月点灯笼 的两个kmp视频
  2. B站视频: av3246487
  3. 知乎文章: https://www.zhihu.com/question/21923021/answer/281346746
#include <iostream>
#include <algorithm>
using namespace std;

int Next[256];
void prefix(string sub);
int kmp(string pat, string sub, int pos = 0);

int main()
{
    string pat, sub;

    cin >> pat >> sub;

    prefix(sub);
    int len = sub.size();
    cout << "子串的前缀数组:" << endl;
    for(int i(0); i<len; i++)
    {
        if(i < len-1)
            cout << Next[i] << ' ';
        else
            cout << Next[i] << endl;
    }

    int tmp = kmp(pat, sub);
    cout << tmp << endl;
    return 0;
}

void prefix(string sub)
{
    int len = sub.size();
    int i(0), j(1);
    Next[i] = 0;

    while(j < len)
    {
        if(i == 0 || sub[i] == sub[j])
        {
            if(sub[j] == sub[i])
                i++;
            Next[j] = i;
            j++;
        }
        else
        {
            i = Next[i-1];
        }
    }
}

int kmp(string pat, string sub, int pos)
{
    int i(pos), j(0);
    int lenpat = pat.size();
    int lensub = sub.size();

    while(i < lenpat && j < lensub)
    {
        if(j == 0 || pat[i] == sub[j])
        {
            if(pat[i] == sub[j])
                j++;
            i++;
        }
        else
        {
            j = Next[j-1];
        }
    }
    if(j == lensub)
        return pos + i - j;
    else
        return -1;
}

运行结果