KMP算法

https://www.acwing.com/solution/content/14666/
人家总结的已经很全面

一：求next的例子

二：算法本质

• 一个是构造出next数组，next数组是对模式串p进行一遍匹配操作，匹配的过程，也是使用next数组的过程，只要是p[i] == p[j + 1] 就让j++，然后更新i，让ne[i] = j，这样就是一个更新next的过程。

• 因为使用的是next[],next数组上面已经看到了，从1到最后，比较的时候实际是s数组的i和p数组的j+1进行比较，出现不匹配的时候调用next[j],因此是i和j+1对应，这样的话，就需要j=0开始，这点一定注意。

#include <iostream>
using namespace std;
const int M = 1e5+ 10, N = 1e6 + 10;
int n, m;
char s[N], p[M];
int ne[M];
int main() {
    cin >> m >> p + 1 >> n >> s + 1;
    // 构造next数组的过程，本质就是下面的匹配过程，用p作为模式串和匹配串
    for (int i = 2, j = 0; i <= m; i++) { // 这里i为2主要是因为next[1]一定是0
        while (j && p[i] != p[j + 1]) j = ne[j]; 
        if (p[i] == p[j + 1]) j++;
        ne[i] = j; // 更新next
    }
    // 利用next数组匹配字符串。
    for (int i = 1, j = 0; i <= n; i++) {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j++;
        if (j == m) {
            cout << i - m << " "; // 题目要求是从0作为开始输出的，所以i-m
            j = ne[j]; //匹配的位置不一定有一个，可能出现多种情况。
        }
    }
    return 0;
}