了解KMP算法，应从传统暴力匹配算法的弊端入手，思考优化方式，并进行分析

传统暴力法过程

用以下两个字符串举例：

S: abababaababacb
M: ababacb

查找S串是否包含子串，暴力解法思路为从S串的第一个字符开始匹配子串，如果不匹配，则从第二个字符重新开始，以此类推。过程如下：

算法实现如下：

显然该方法的时间复杂度为O(mn)，其中m为主串S的长度，n为子串M的长度

KMP算法思路

反思暴力法，其最大的问题就是每次都会将j指针重置，并将i指针移动到上次匹配开头的下一位，原本已经匹配完的部分完全没有发挥作用，造成了浪费。
KMP算法的核心思想就是从已经匹配的部分获取信息，使i指针不进行回溯
通过观察第一次失败时已经匹配完成的串：ababa，我们可以发现它的前三个字符和最后三个字符是一样的，即aba。因此，其实我们通过右移S串，将这两个aba对齐，如下所示：

a b a b a b a a b a b a c b
     a b a b a c b

这个操作对人类而言很好理解，但计算机要如何知道移动多少距离呢？为了解决这个问题，我们需要先认识三个概念：

字符串的前缀、后缀和部分匹配值

字符串的前缀，指的是除了最后一个字符以外，该字符串的所有头部子串；字符串的后缀则相反，指的是除了第一个字符以外，该字符的所有尾部子串；而部分匹配值，指的是字符串的前缀和后缀交集中长度最大的子串。概念比较不直观，下面我们以S:ababacb为例，了解这三个概念。

我们将字符串S分为长度依次增加，均以S的第一个字符为开头的子串集合：

并分别考察这些子串的前缀、后缀及部分匹配值：

1. a 的前后缀均为空集(因为前后缀均不包括对应端点)，交集也为空集，记部分匹配值为0

2. ab 的前缀为{a}，后缀为{b}，交集为空集，部分匹配值为0

3. aba 的前缀为{a, ab}，后缀为{a, ba}，交集为{a}，长度为1，因此部分匹配值为1

4. abab 的前缀为{a, ab, aba}，后缀为{b, ab, bab}，交集为{ab}，长度为2，因此部分匹配值为2

5. ababa 的前缀为{a, ab, aba, abab}，后缀为{a, ba, aba, baba}，交集为{a, aba}，最长元素的长度为3，因此部分匹配值为3

6. ababac 的前缀为{a, ab, aba, abab, ababa}，后缀为{c, ac, bac, abac, babac}，交集为空集，因此部分匹配值为0

7. ababacb 的前缀为{a, ab, aba, abab, ababa, ababac}，后缀为{b, cb, acb, bacb, abacb, babacb}，交集为空集，因此部分匹配值为0

梳理完毕后，我们可以得到一个关于串S的部分匹配值表: [0, 1, 2, 3, 0, 0]，这个表在KMP算法中至关重要。

计算子串应该右移的距离

我们回头观察第一次发生不匹配的情况：

观察已经匹配的这部分子串(标绿部分)，即ababa，通过刚才的部分匹配值表，我们可以得到它最后一个字符的部分匹配值为3。从定义可知，这个值表示了ababa这个字符串拥有一个长度为3的，相等的前缀和后缀，很显然该字符串为aba。此时我们让S串中的前缀aba与M串中的后缀aba对齐，如下图所示：

此时 i 指针之前的aba确定是匹配好的，因此不需要移动 i 指针。关于 j 指针的移动将在下文介绍，此处我们考察S串右移的距离：

我们将已经匹配完毕的字符串记为A，很显然，我们的操作为将A中最长的相同前后缀对齐，对齐方式为M串中A的后缀对齐S串中A的前缀，因此我们的移动距离就应该是：

我们不难发现 length(A) = j，将部分匹配值表记为 next，我们可以得到如下关系式：

回溯 j 指针

在上述移动S串后的图中，很容易看出来我们需要将j指针移动到i指针的正下方以便继续进行匹配，如下图：

该位置其实就是S串去除掉A串后的第一个位置，因为前面已经可以确保完全匹配，因此从该位置继续往下匹配即可。因此我们可以列出先前的j指针位置(j_old)和移动后的j指针位置(j_new)的关系式：

通过以上式子，我们可以阐述出KMP算法的步骤：

1. 求出S串的next表

2. 使用i、j指针对M串与S串逐字匹配

3. 匹配，则i和j指针均向后移动

4. 不匹配，i指针不动，j指针置为next[j-1]

5. 重复2~4

基于以上思路，我们可以写出KMP算法的代码实现(假设我们已经写好了可以求next表的函数get_next)：

next表的求法

KMP算法核心为next表，我们需要高效地得到子串的next表，才能继续执行KMP算法。next表的计算方式主要有两种，一种即为上述介绍next表概念时的手算法，下文主要介绍第二种。

仍以串Sababacb为例，我们观察其next表获得的过程

观察next[0]，由于a的前后缀均为空集，所以next[0]必然为0
观察next[1]，由于新增字符b与a不同，因此前后缀仍为空集，next[1]=0 观察next[2]，观察到新加入的a与第一个a可以产生一个相同的前后缀，长度为1，所以next[2]=1，如图所示：

观察next[3]，加入了一个新的b，发现刚刚匹配的a后面也有一个b，他们可以组成更长的前后缀，因此next[3]=next[2]+1=2，如图所示：

观察next[5]，此时c加入，无法继续延长前后缀，这种情况应该怎么处理呢？

现在我们已经掌握了第一个规律，即加入与之前相同的字符可以延长前后缀的规律，我们以j代表next表的指针，我们分析：

“已经找到的最长前后缀中前缀的后一个字符"的位置，其实就是j-1位置的next值，因为next[j-1]为串S的前j-1个字符的最长相同前后缀的长度，而他的下一个字符的下标，就是next[j-1]

了解了这个规律后，我们用一个新的例子来帮助理解当新加入的字符与前面不同时，即：

S[next[j-1]] != S[j]

时，应该如何处理。

我们记串abacabab为B，先给出其next[0]~next[6]的值，如图：

考察next[7]时，发现无法继续组成更长的前后缀了。因此我们应该放弃“延长最长前后缀”的思路，去找找那些不是最长的前后缀，是否可以进行延长。思路如下：

1. 我们需要考察b前面已经找到的最长前后缀里，是否可以和b组合延长的前后缀，也就是在上图标橙的aba里找

2. 也就是将问题转化成向aba串中加入字符b，应该如何计算其部分匹配值

3. 因此我们需要aba的next表，来尝试是否可以重新利用规律1

4. 正巧，aba的next表在绿色的那一块已经完成了

我们可以发现这个已经找到的最长前后缀的长度其实就等于next[j-1]。接下来我们尝试利用规律1

为了方便，我们令curr=next[j-1]，并得到完整的求next表函数：

至此KMP算法结束，在撰写过程中笔者也深感知识储备不足，难以用言语简单地表述清楚，写下此篇主要为检测自身掌握情况，并在未来做复习用