串与模式匹配算法

思维导图：点我

一、数据结构

1. 定长顺序存储结构

2. 堆分配存储结构

3. 块链存储结构

4. 赋值操作

5. 复制操作

6. 判空操作

7. 比较操作

8. 求串长

9. 求子串

10. 串连接

11. 清空操作

12. 销毁串

二、朴素模式匹配算法

三、KMP 算法

由简单的朴素模式匹配算法可以发现，在匹配字符时，有一些字符先前已经匹配过了，但是在匹配到下一个字符时会重复与之进行匹配，这就造成了效率上的浪费，因此为了充分利用前面的工作成果，出现了 KMP 算法。

KMP 算法比朴素的模式匹配算法有优势的地方在于不需要回溯。朴素的模式匹配的时间复杂度需要，也就是两个字符串的长度相乘。而当我们使用 KMP 算法的时候，会使用子串来算出一个 next 数组，当我们在比较的时候，可以根据next数组的，移动子串与主串的对比位置。时间复杂度是。也就是两个字符串的长度相加。

虽然 KMP 算法的时间复杂度远低于朴素模式匹配，但并不代表就能全面取代它。因为在大部分情况下朴素模式匹配其实已经足够快，而 KMP 算法要求主串有较多的和子串匹配的片段，更适用于这类情况。

为了解 KMP 算法，首先需要了解一些基础概念：

前缀：除最后一个字符外，字符串的所有头部子串。

后缀：出第一个字符外，字符串的所有尾部子串。

部分匹配值：字符串的前缀和后缀的最长相等前后缀长度。

举个栗子：

'a' 的前缀和后缀都为空集，部分匹配值为 0 。

'ab' 的前缀为 {a} ，后缀为 {b} ，部分匹配值为 0 。

'aba' 的前缀为 {a, ab} ，后缀为 {a, ba} ，部分匹配值为 1 。

'abab' 的前缀为 {a, ab, aba} ，后缀为 {b, ab, bab} ，部分匹配值为 2 。

'ababa' 的前缀为 {a, ab, aba, abab} ，后缀为 {a, ba, aba, baba} ，部分匹配值为 3 。

因此字符串 'ababa' 的部分匹配值为 00123 。

假设此时有一个主串为

，子串为

，则得到子串的部分匹配值：

编号	1	2	3	4	5
S	a	b	c	a	c
PM	0	0	0	1	0

第一趟匹配过程中，发现

与

不匹配，那么说明前面的两个字符

是匹配的，查表发现

所对应的部分匹配之为 0 ，因此可以通过下面的公式计算出子串需要向后移动的位数：

因此，所以将子串向后移动 2 位：

主串

子串

ㅤ

此时发现

与

不匹配，继续进行上述操作：

主串

子串

ㅤ

此时匹配成功。为了使算法更加简洁明了，我们需要对公式进行优化，首先将公式换个写法，式中表示当前匹配失败的位置：

由于子串末位的部分匹配值不会用到，又因为每当进行匹配操作的时候，通常影响子串跳跃的位置是在匹配失败的位置，然而我们需要使用的值是前一位的部分匹配值，因此可以将 PM 表的值整体右移一位，得到新的

表：

编号	1	2	3	4	5
S	a	b	c	a	c
next	-1	0	0	0	1

我们将右移后的首位部分匹配值用 -1 代替，这样若第一个元素匹配失败，则只需要将子串右移一位。此时公式就变为：

我们注意到公式中有一个

的操作，这显得有点多余，因此我们可以将

值整体加1，使公式更加简洁：

此时表为：

编号	1	2	3	4	5
S	a	b	c	a	c
next	0	1	1	1	2

而对子串右移

位实际上就是将子串指针指向

的位置，因此我们只需要在匹配失败的时候将子串的指针位置改变即可。

此处给出求 next 数组的算法：

接下来考虑对 next 数组进行改进。

我们考虑一个实例：

S	a	a	a	b	a	a	a	a	b
P	a	a	a	a	b	ㅤ	ㅤ	ㅤ	ㅤ
j	1	2	3	4	5	ㅤ	ㅤ	ㅤ	ㅤ
next[j]	0	1	2	3	4	ㅤ	ㅤ	ㅤ	ㅤ
nextval[j]	0	0	0	0	4	ㅤ	ㅤ	ㅤ	ㅤ

当 i = 4、j = 4 时，跟失配，如果用 next 数组还需要进行跟者三次比较，然而这几次比较毫无意义。

问题在于不该等于。因为当时，下次匹配必然是跟进行，如果，则本次比较毫无意义。

因此当这种情况发生时，应该将 next[j] 修正为 next[next[j]]，直至两者不相等为止，更新后的数组命名为 nextval ，代码如下：

有了 nextval 数组，就可以实现 KMP 算法了：