题目

$kmp$ 算法要解决的问题就是给定两个字符串，一个主串，一个模版串，判断模式串是否在主串里，$AcWing$是求出现了多少次，基本上都是这样。

思路

所有算法题的大体思路几乎都是：

1. 暴力算法怎么做
2. 如何优化

暴力算法

假设$s[n]$是主串，$p[m]$是模版串。

for (int i = 1; i <= n; i++){ // 遍历主串
    bool flag = true;
    for (int j = 1; j <= m; j++){ // 对于每个以S[i]开头的串，判断是否相等。
        if (s[i + j - 1] != p[j]){ // y总原来打错了，现在改过来了。
            flag = false;
            break;
        }
    }
}

优化

假如$s$串枚举到$i$点，然后前$j$个字符一样，第$j+1$个字符不一样了，按照暴力的思路，应该把$p$串往后移，但这样前面遍历的就白费了，所以我们要找某种性质。

把$p$串往后移之后，如果还是到$j$这个地方，就说明一开始没移动的那一部分，前$j$个字符有一段前缀和后缀相等，我们要找出最长的，因为这样往后移的距离越短。
那么就可以发现，这些东西都是跟$p$串有关系。

我们就可以预处理相等的前后缀的长度最大是多少，这就是$kmp$中最难的$next$数组的含义。

这样就可以定义$next$数组了

$next$数组的定义

$next_i$ 就等于以$i$为终点，最长的、前后缀相等的前后缀的长度（真绕）。

假如next[i] = j，那么就说明$p_1$ ~ $p_j = p_{i-j+1}$ ~ $p_i$

那么在匹配的过程中，这个东西怎么运用呢？

如果主串匹配到$i-1$，模版串匹配到$j$了，都一样，但下一个位置就不一样了，那么模版串要往后移，原来$i$的位置正好可以变成$next[j]$继续匹配，如果不成功再往后来。
然后就结束了。

代码（就当成模版吧）

#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
char p[N], s[M];
int ne[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    // 求next的过程
    for (int i = 2, j = 0; i <= n; i ++ )
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }

    // kmp匹配功能
    for (int i = 1, j = 0; i <= m; i++) // j要和i错开一位
    {
        while (j && s[i] != p[j + 1]) j = ne[j]; // 如果不匹配，就往后移。
        if (s[i] == p[j + 1]) j++; // 如果匹配j就移到下一个位置。
        if (j == n) // 匹配成功!
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }

    return 0;
}

结束