对KMP算法的一点碎碎念——上篇

对KMP算法的一点碎碎念——上篇

1. KMP 算法 Next数组 求解问题

假设有模式串T为：a b a b a c，求解与其对应的next数组为多少

1.1 前置知识-最长公共前后缀LCP

1.1.1 前缀与后缀

前缀的概念：前缀是 不包含最后一个字符 的所有 以第一个字符开头 的任意子串

后缀的概念：后缀是 不包含第一个字符 的所有 以最后一个字符结尾 的任意子串

例如字符串 “aba”

1. 去掉最后一个字符后，剩下的都是前缀了

   $ab\xcancel{a}$，这里 ab 就是这个字符串的其中一个前缀

2. 同理去掉第一个字符后，剩下的都是后缀了

   $\xcancel{a}ba$，这里 ba 就是这个字符串的其中一个后缀

为什么这里我说是其中一个前/后缀呢？

回到前后缀的概念上，前后缀都是以子串的形式存在的，也就是说，前后缀一定是模式串的子集

那么就好理解了，aba的前后缀表如下：

前缀	后缀
a	a
ab	ba

---

1.1.2 最长公共前后缀LCP

概念：最长公共前后缀 (longest common prefix) 就是字符串中前缀和后缀的 最长匹配子串

例如，“aabaa”，我们从 前缀(prefix)和后缀(suffix) 中寻找最长的匹配子串

字符串 aabaa 的子串	前缀(去掉最后一个字符)	被去掉的字符	后缀(去掉第一个字符)	被去掉的字符	前后缀最长匹配数(就是next值)
a	✗	$\xcancel{a}$	✗	$\xcancel{a}$	0
aa	a	$a\xcancel{a}$	a	$\xcancel{a}a$	1
aab	a, aa	$aa\xcancel{b}$	b, ab	$\xcancel{a}ab$	0
aaba	a, aa, aab	$aab\xcancel{a}$	a, ba, aba	$\xcancel{a}aba$	1
aabaa	a, aa, aab, aaba	$aaba\xcancel{a}$	a, aa, baa, abaa	$\xcancel{a}abaa$	2

---

1.2 手算法求解 Next数组值(3种常见情况)

由于KMP算法中的next数组有不同的实现方式，因此为了避免大家弄混淆，我对每个实现next数组的方法做一些区分

1.2.1 情况1: next数组 正常存放匹配字符的长度

这是最常见的情况，基本上网络上大部分都是以这个情况为主来求解next数组值，我们上面也讨论过了next值如何得出

以模式串 “ababac” 为例，完整的next数组如下：

模式串下标	0	1	2	3	4	5
模式串	a	b	a	b	a	c
next数组值	0	0	1	2	3	0
匹配的前后缀	✗	✗	a b a 匹配位为前后缀 ‘a’	a b a b 匹配位为前后缀 ‘a b’	a b a b a 匹配位为前后缀 ‘a b a’	✗

我们可以发现，每个字符下的next数组值都是存放着当前串的匹配长度

初学者可能会对第4个位置有疑惑，咱们一起来看如何求解？

模式串匹配到第4个字符后，前4个字符组成了一个串，即"ababa"

• 前缀的集合为：$a,ab,aba,abab$

• 后缀的集合为：$a,ba,aba,baba$

通过观察，我们可以看到集合中 $aba$ 为最长公共前后缀，且长度为3

情况1的失配回溯机制

假如文本串(主串)为 “abababac”，模式串为 “ababac”，在下标为5的位置发生失配

从图中我们看出：

1. 左侧图，当主串S和模式串T比较到下标为5的位置时，发现主串和模式串不匹配，故模式串的指针j需要回退，回退的顺序为

   1. 寻找找从当前失配位置的前一位，它的next值是多少？

      当前失配位置为下标5，它前一位的next值为3

   2. 前一位的next值就是j要回退的位置的下标

      那么j要回退的位置就是 j = next[j-1] = next[4] = 3

2. 右侧图，我们已经找到回退的位置了，故j回到下标为3的位置上继续与主串S重新匹配

还有一种的实现方式是和这个原理一样的，就是把这所有的next数组值减1，然后找回溯位置时再把next值加1而已

模式串下标	0	1	2	3	4	5
模式串	a	b	a	b	a	c
next数组值	-1	-1	0	1	2	-1

回溯位：j = next[j-1] + 1

不难看出，虽然好理解，但是操作很繁琐。每一次j失配都需要找前一位的next值作为自己的回退位置，这时候有人对next数组做出了改进，当在当前位置失配时，直接获取当前失配位置的next值作为j回退的位置，这就是我们要讲解的下一种情况

---

1.2.2 情况2: next数组 整体右移一位

以模式串 “ababac” 为例，完整的next数组如下：

模式串下标	0	1	2	3	4	5
模式串	a	b	a	b	a	c
next数组值	-1	0	0	1	2	3
匹配的前后缀	✗	✗	✗	a b a 匹配位为前后缀 ‘a’	a b a b 匹配位为前后缀 ‘a b’	a b a b a 匹配位为前后缀 ‘a b a’

你可能会疑惑，这样做也没什么区别啊，反而更难理解了？实则不然，我们看下面的比较方式就能看出来了

字符串匹配最本质的原理其实就是前后缀相匹配的问题，我们把模式串右移一位，在逻辑上更符合匹配的情况，这就是为什么大部分教程和书籍都用这两种方式讲解next数组值的原因。那么，除了逻辑上更符合之外，还有next数组右移一位还有什么优势呢？我们再看下面的图解

情况2的失配回溯机制

假如文本串(主串)为 “abababac”，模式串为 “ababac”，使用右移模式串T的方式与主串S进行匹配

当前位置不匹配，那么就直接从不匹配的位置获取next数组值，然后j就回退到当前位置的next对应的下标位置。对齐的那个地方不算一个步骤，只是为了让大家更好理解

通过以上图片对比，我们发现把next数组整体右移一位在一定情况下的匹配效率更高，这就是为什么右移next数组这么流行的原因了

回溯位：j = next[j]

---

1.2.3 情况3: next数组 整体右移一位并把next数组加1

以模式串 “ababac” 为例，完整的next数组如下：

模式串下标	0	1	2	3	4	5	6
模式串	✗	a	b	a	b	a	c
next数组值	✗	0	1	1	2	3	4
匹配的前后缀	✗	✗	✗	✗	a b a 匹配位为前后缀 ‘a’	a b a b 匹配位为前后缀 ‘a b’	a b a b a 匹配位为前后缀 ‘a b a’

其实情况3的实现方式和情况2是一样的，只不过我们发现情况3的next数组的初始位置是从1开始，而情况1的next数组的初始位置是从0开始的

不过我个人认为，情况3更像是情况1和情况2的结合，它杂糅了它们的思想，为什么这么说？先给出结论

1. 在回溯机制上，情况3的回溯机制思想和情况2的回溯机制思想是一样的

   都是当前位置不匹配，那么就直接从不匹配的位置获取next数组值，然后j就回退到当前位置的next对应的下标位置

   情况3的回溯机制也就是 j = next[j]
   而不是情况1的 j = next[j-1]
   

2. 在next数组值确定上，情况3的数组值确定方式和情况1是一样的

   都是从当前位置及之前构成的串中寻找 最长公共前后缀，然后把匹配的值确定为当前位置的next值

情况3的失配回溯机制

假如文本串(主串)为 “abababac”，模式串为 “ababac”，使用右移模式串T并把下标加1的方式与主串S进行匹配

回溯位：j = next[j]

---

参考资料

KMP算法之求解next数组 (xiaohongshu.com)

帮你把 KMP 算法学个通透！（理论篇）

帮你把KMP算法学个通透！（求next数组代码篇）

KMP 算法之求next数组代码讲解

KMP算法精讲（1）——暴力匹配算法

KMP算法精讲（2）——什么是最长公共前后缀？

KMP算法精讲（3）——最长公共前后缀在KMP算法中的应用

KMP算法精讲（4）——15分钟搞定next数组

KMP Algorithm for Pattern Searching - GeeksforGeeks

Prefix function - Knuth-Morris-Pratt Algorithm - Coding Ninjas