（一） KMP模板

优化思路

先打暴力，从过程中发现重复的操作，进行优化。

一、暴力 $~O(mn)~$

枚举字符串中每一个位置作为模式串的起点，尝试匹配。
核心代码：

for (int i = 1; i <= m; i ++ )
{
    bool flag = true;
    for (int j = 1; j <= n; j ++ )
        if (s[i + j - 1] != p[j])
        {
            flag = false;
            break;
        }

    if (flag) cout << i - 1 << " ";
}

二、优化

我们发现，如果当前尝试行不通，我们之前已经在第二重循环中扫过的区域有很大一块会再次被扫到。如图

那么KMP就是通过一些空间消费，优化了这一块，使得我们可以通过预处理的信息将${\color{Red} {模式串}}$的位置直接移到${\color{Orange} {下一个合理的位置}}$

1.利用预处理优化算法

在一次枚举匹配中，对于模式串从开头到最后一个正确的位置（也就是紫竖线之前的那一块，下称大区间），如果我们能够从大区间中找到两个小区间，保证两个小区间是完全相等的，并且第一个区间的开头是模式串的开头，第二个区间的结尾是大区间的结尾（也就是紫竖线前最后一个可以匹配的元素），那么我们可以将模式串的开头“移”（以下记此操作为平移）到第二个区间的开头（也就是让整个模式串跟着第一个区间平移到了第二个区间），形成下一次匹配的情形。
此时，我们无需判断新情形中${\color{Brown}{紫竖线前面的一块}}$是否符合要求。从而避免了重复的“扫”。

至于为什么无需判断，我们看到第二个区间一定符合字符串$S$的部分区域，而第一个区间和第二个区间又是完全相等的，所以平移过去不会影响这一块的匹配。

而为了不漏所有的可能，我们当然希望每次平移都能够移动较少的距离，也就是说要看大区间内第一、第二区间的最长长度（自行模拟可知）。

而KMP就是来预处理这样的信息。

$next[i]$就是来储存模式串$p$中从下标$~1~$（即模式串开头）到下标$~i~$这个大区间中第一、第二区间的最大长度。
即：
$$~next[i]~储存的是满足 ~p[1,~ j] = p[i-j+1,~ i]~ 的~j~的最大值$$

2.怎么求$~next[i]~$呢？

我们按照顺序从模式串中从左到右求$~next[i]~$，就可以使用前面已经处理过的$~next~$值了。
我们尝试使用$~next[i-1]~$增值到$~next[i]~$
如图：

如果相等，那么$~next[i]~$就出来了。
如果不相等，我们继续缩小考察的区间，直到找到相等的。

三、正解 $~\Theta(m+n)~$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

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

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

    // 求 next[i]
    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 ++;    // 这里 j 就是当前第一第二区间的长度了。因为 j 有可能变为 0，所以这里要判断。
        /* 出现相等，那么 第一第二区间可以吸收 p[j + 1] 和 p[i]，于是 j ++ 。
        同时为下一步查找奠定查找范围 j 的基础。 */
        ne[i] = j;   // 记录 next[i]。
    }

    // 匹配
    for (int i = 1, j = 0; i <= m; i ++ )   // 为字符串中第 i 个元素匹配元素。
    {
        while (j && s[i] != p[j + 1]) j = ne[j];  
        /* 当找到字符串和模式串不能互相匹配的地方时，
        就不断的平移变换（将模式串向右“移”），直到可以匹配。
        */
        if (s[i] == p[j + 1]) j ++;   // 这里 j 就是能够匹配 i 的第一第二区间最大长度。判断理由同上。
        if (j == n)  // 匹配成功。
        {
            printf("%d ", (i - n + 1) - 1);   // -1 因为题目以 0 开始记录。
            j = ne[j];   // 还是继续平移，而不是 j ++ 
        }
    }

    return 0;
}

（二） 习题

更好地认识 next 数组
KMP 与 dp 相结合