kmp，字符串匹配算法。

举个例子

文本串 aabaabaaf
模式串aabaaf

前缀表

存储 最长相等的前后缀 长度？——值得注意的是 相等 不是对称相等，而是完全相等。ab==ab ab!=ba
先根据模式串初始化前缀表

前缀表有人称为 next 数组， 也有人写 prefix 数组。我这里写 next 数组

前缀表的使用

在匹配到不同字符之后， 看该字符的前一位的前缀表所对应的值， 将比较指针跳到对应的值下标处。
也就是 j = next[j-1]
有些教学可能不是直接看前一位，但是具体原理都是差不多的。
核心：遇见冲突位置，要向前回退。

void kmp(const string& s, const string& p) {
    for (int i = 0, j = 0; i < s.length(); ++i)
    {
        while (j && s[i] != p[j]) j = next[j - 1];// 不断前移j指针，直到成功匹配或移到头为止
        if (s[i] == p[j]) j++;  // 当前位匹配成功，j指针右移
        if (j == p.length())
        {
            // 对s[i - j + 1 .. i]进行一些操作
            j = next[j - 1];
        }
    }
}

怎么获得前缀表

如果暴力去求，那就没意思了。时间复杂度，那等于没用kmp。巧妙的做法是：错开一位后，让模式串匹配自己——相当于是 前缀去匹配后缀。
很明显，next[0] == 0，之后的每一位就通过匹配中记录 j 的值获得。

// next[0] = 0;
void get_next(const string& p) {
    for (int i = 1, j = 0; i < plen; ++i)
    {
        while (j && p[i] != p[j])  // 遇见冲突
            j = next[j - 1];
        if (p[i] == p[j]) j++;
        next[i] = j;
    }
}

来点题目

P3375 【模板】KMP字符串匹配

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int next[MAXN];
void get_next(const string& s) {
    for (int i = 1, j = 0; i < s.length(); ++i) {
        while (j && s[i] != s[j]) j = next[j - 1];
        if (s[i] == s[j]) j++;
        next[i] = j;
    }
}
void kmp(const string& s, const string& p) {
    for (int i = 0, j = 0; i < s.length(); ++i) {
        while (j && s[i] != p[j]) j = next[j - 1];
        if (s[i] == p[j]) j++;
        if (j == p.length()) {
            cout << i - j + 2 << '\n'; // 因为要1-index，所以是+2
            j = next[j - 1];
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    string s, p;
    cin >> s >> p;
    get_next(p);
    kmp(s, p);
    for (int i = 0; i < p.length(); ++i)
        cout << next[i] << ' ';
    return 0;
}