C＋算法进阶系列之从 Brute Force到KMP 字符串匹配算法

1. 字符串匹配算法

所谓字符串匹配算法，简单地说就是在一个目标字符串中查找是否存在另一个模式字符串。如在字符串 "" 中查找是否存在 “****” 字符串。

可以把字符串 ""  称为原始（目标）字符串，“**” 称为子字符串或模式字符串**。

本文通过如下 种字符串匹配算法之间的差异性来探究 算法的本质。

2. BF(Brute Force，暴力检索)

BF 算法是一种原始、低级的穷举算法。

2.1  算法思想

如下使用长、短指针方案描述 BF 算法：

初始指针位置： 长指针指向原始字符串的第一个字符位置、短指针指向模式字符串的第一个字符位置。这里引入辅助指针概念，并不是必须的。

Tips： 辅助指针是长指针的替身，替长指针和短指针所在位置的字符比较。每次初始化长指针位置时，让辅助指针和长指针指向同一个位置。

如果长、短指针位置的字符不相同，则短指针不动、长指针向右移动。如果长、短指针所指位置的字符相同，则用辅助指针替代长指针（长指针位置不动）和短指针位置的字符比较，如果比较相同，则同时向右移动辅助指针和短指针。

如果辅助指针和短指针位置的字符不相同，则重新初始化长指针位置（向右移动），短指针恢复到最原始状态。

借助循环或者递归的方案重复上述流程，直到出口条件成立。

查找失败：长指针到达了原始字符串的尾部。当 长指针位置=原始字符串长度 - 模式字符串长度+1 时就可以认定查找失败。

查找成功： 短指针到达模式字符串尾部。

2.2 编码实现

2.2.1  使用辅助指针

使用辅助指针替代长指针和短指针所在位置的字符进行比较。

测试：

输出结果：

2.2.2  使用增量

以长指针为参照起点，需要比较时，以相对增量位置和短指针位置字符比较。

2.2.3 长指针和短指针直接比较

在原始字符串和模式字符串开始逐一比较时，最好不要修改长指针的位置，否则，在比较不成功的情况下，重修正长指针的逻辑有点繁琐。

2.3 BF 算法的时间复杂度

算法直观，易于实现，但是缺少变通，是典型的穷举思想。

如果原始字符串的长度为 ，模式字符串的长度为 。时间复杂度则是 ，时间复杂度较高。

3. RK（Robin-Karp 算法）

算法 ( 指纹字符串查找) 在 算法的基础上做了些改进，基本思路：

如下图示，和比较 次后，才发现两者匹配不上，意味着前面的 次比较，除了浪费时间，无其它意义。能不能通过一种算法，快速判断出本次比较是否有必要进行。

3.1 RK 的算法思想

选定一个（可自定义）。

使用哈希函数计算模式字符串的哈希值。如上计算 的哈希值。

再从原始字符串的开始比较位置起，截取一段和模式字符串长度一样的子串，也使用哈希函数计算哈希值。如上计算 的哈希值。

如果两次计算出来的哈希值不相同，则可判断两段模式字符串不相同，没有开始比较的必要。

如果两次计算的哈希值相同，因存在哈希冲突，还是需要使用 算法进行逐一比较。

算法使用哈希函数算法杜绝了不必要的比较。

3.2 编码实现：

RK 的时间复杂度：

的代码逻辑和 一样，但内置了哈希判断。如果原始子符串长度为 ，模式字符串的长度为 。时间复杂度为 ，如果不考虑哈希冲突问题，理想状态下的时间复杂度可以为 。

很显然 算法比 算法要快很多。

4. KMP算法

算法的本质是穷举，这是由计算机的思维方式决定的。

我们谈论"好"、“坏” 算法时，所谓的指能让穷举的次数少一些。比如前面的 RK 算法，通过一些特性提前判断是否值得比较，这样可以省掉很多不必要的内循环。

KMP 也是一样，也是尽可能减少比较的次数。

4.1 KMP 算法思想

KMP 的基本思路和 BF 是一样的（字符串逐一比较）。但在 算法做了性能上的优化。

让我们再次回到前面的比较流程中。如下图所示，在比较 次后，辅助指针和短指针对应位置字符不相同，说明匹配失败。

的做法是，让长指针向右移一位，短指针恢复原始状态。再重新逐一比较。

但是，这里应该会有一个思考？难道前面的 次成功的比较就没有一点可利用的价值吗？

那就再回放，仔细观察一番。

会发现一个有趣的地方。部分匹配成功的字符串，在原始字符串中的后面的字符和模式字符串的前面的字符是相同的。如下填充灰色区域。

直观告诉我们，长指针可以不用回到最初开始的位置，只需要让短指针稍微回一下。

如下图所示：

很明显示缩短了很多不必要的比较次数。

那么这个现象有没有通用性？

再分析如下   个字符串的比较，即使前面有 次比较成功，当匹配失败后，长指针确实可以不用移动，但是短指针必须回到最初位置，再重新开始。

那么在什么情况下可以让短指针只做稍微的移动？

说清楚这个问题之前，先理解几个概念：

前缀集合：

如： 的前缀（不包含字符串本身）集合。

后缀集合：

如：**** 的后缀（不包含字符串本身）集合 。

PMT值： 前缀、后缀两个集合的交集元素中最长元素的长度。

如：先求  和  的交集，得到集合 ，再得到集合中最长元素的长度， 所以   字符串的   值是 。

一通前缀、后缀、交集概念说完后，但其结论很简单：仅当共同匹配成功的，其和有相同的部分时，方可以减少短指针的移动量。当相同部分越多，短指针移动的量就越小。

这里就有 个问题又摆在面前。

如何知道已经匹配成功的字符串有公共的和以及最大相同长度值。

如何根据最大值修正短指针的位置。

如上的 个问题，便是 算法的核心。会把这些信息存储中 “****”中，修改短指针的位置便是根据这个表中数据。

4.2 PMT 的计算

KMP 算法中 的 "部分匹配表（PMT）" 是怎么计算出来的？

如前面图示，原始字符串和模式字符串逐一比较时，前 位即 是相同的，而 存在最大长度的前缀和后缀 ‘’ 子串。意味着下一次比较时，可以直接让模式字符串的前缀和原始字符串中已经比较的字符串的后缀对齐。

这些信息都是从表中获取。所以，**** 算法的核心是得到 表。

现使用手工方式计算 的 值：

当仅匹配第一个字符  时， 没有前缀集合也没有后缀集合，所以 ，短指针要移到模式字符串的 位置。

当仅匹配前二个字符 时，的前缀集合，后缀集合是，没有交集。通俗理解，不存在前后相同部分。所以 ，短指针要移到模式字符串的 0 位置。

当仅匹配前三个字符 时， 的前缀集合 ，后缀集合，交集。所以 ，短指针要移到模式字符串 的位置。

当仅匹配前四个字符 时， 的前缀集合 ，后缀集合，交集，所以 ，短指针要移到模式字符串 的位置。

当仅匹配前五个字符 时， 的前缀集合,后缀集合，没有交集，所以，短指针要移到模式字符串的 位置。

当全部匹配后，意味着匹配成功。所以 。

其实在 算法中，没有直接使用 表，而是引入了 数组的概念， 数组中的值是 的值向右移动一位。

KMP算法实现： 先不考虑 数组的算法，暂且用上面手工计算出来的值作为 算法的已知数据。

上面的代码没有通用性的，现在实现求解 数组的算法。

求 也可以认为是一个字符串匹配过程，只是原始字符串和模式字符串都是同一个字符串。本质是在匹配成功的字符串中查找和相同子字符串的数量。

当仅匹配一个 。没前缀和后缀。则 。

当匹配 个。如下图，前缀、后缀没有相同的部分。则 。

当匹配 个。如下图，其前缀、后缀有一个字符 相同。则 。

当匹配 个。如下图，其前缀、后缀 字符串相同。则 。

当匹配 个。如下图，其前缀、后缀没有相同。则 。

全部匹配，表示程序匹配成功。值为 。

编码实现：

算法的时间复杂度可以达到 。但是，如果模式字符串中不存在相同的前缀和后缀时，时间复杂度接近算法。

5. 总结

字符串匹配算法除了上述几种外，还有 等算法。

从暴力算法开始，其它算法都是在尽可能减少计算次数，提高算法的运行速度。