> For the complete documentation index, see [llms.txt](https://wandersofb.gitbook.io/blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wandersofb.gitbook.io/blog/suan-fa/ji-chu/kmp.md).

# KMP

学习 KMP 算法最好还是先背模板，写个几遍之后就理解的差不多了。

### next 数组

next 数组可以认定为一个状态转移数组，其含义是最大前缀和后缀的相同的值的数量。这个解释不够清晰。举个例子：

$$
a\ b\ a\ a\ b\ c\ a\ c
$$

$$
0\ 0\ 1\ 1\ 2\ 0\ 1\ 0
$$

其中的值也可以认定为当我在当前位置匹配失败了，要回退的 index - 1。那么我在前面加个空格，就是正常的回退 index。

#### 那么如何求 next 数组？

先看一下代码。

```cpp
for (int i = 2, j = 0; i <= m; i ++) {
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++;
    ne[i] = j;
}
```

求解 next 数组类似于双指加回溯。i 指针一直递增，j 指针指向的前面的字符和 i 指针前面的部分字符相同。当二者指向的字符相同时，二者都增加，但当不同时，j 需要回溯向前找到最长的那个字符，看它的下一位是否和 i 指向的字符是否相同，不同再回溯。回溯的过程，由于一直都是再找最大的那个，所以是最优解。

### 模式匹配

```cpp
for (int i = 1, j = 0; i <= m; i ++) {
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++;
    if (j == n) {
        cout << i - n << ' ';
        j = ne[j];
    }
}
```

求解出 next 数组就简单了，模式匹配的思路和求解 next 数组一模一样。当匹配时，都向前，但当不匹配时，就向前回溯，找到最最适合的，看后一位时候匹配。