博文地址

目录

• 目录
• 32 | 字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？
  • BF 算法
  • RK 算法
    • 哈希算法的设计
    • 哈希算法的规律
    • 时间复杂度分析
    • 引入散列冲突
    • 总结

32 | 字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？

编程语言提供的字符串查找函数，底层依赖的就是字符串匹配算法，比如 Java 中的 indexOf()，Python 中的 find() 等。

• 单模式串匹配算法：一个串跟一个串进行匹配，BF、RK、BM、KMP
• 多模式串匹配算法：在一个串中同时查找多个串，Trie 树、AC 自动机

主串和模式串：在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。

BF 算法

BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。

假设主串的长度为 n，模式串的长度为 m，因为是在主串中查找模式串，所以 n > m。

作为最简单、最暴力的字符串匹配算法，BF 算法的思想用一句话来概括就是：在主串中，检查起始位置分别是 0、1、2....n-m 且长度为 m 的 n - m + 1 个子串，看有没有跟模式串匹配的。

在极端情况下，每次都比对 m 个字符，要比对 n - m + 1 次，所以，这种算法的最坏情况时间复杂度是 O(n * m)。

尽管理论上的时间复杂度很高，但在实际的开发中，BF 算法却是一个比较常用的字符串匹配算法：

• 原因一：时间复杂度并没有那么大
  • 大部分情况下，模式串和主串的长度都不会太长，所以 n * m 的值并不会很大
  • 每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，不需要把 m 个字符都比对一下
• 原因二：简单
  • 朴素字符串匹配算法思想简单，代码实现也非常简单。简单意味着不容易出错，如果有 bug 也容易暴露和修复。
  • 在工程中，在满足性能要求的前提下，简单是首选。这也是我们常说的 KISS（Keep it Simple and Stupid）设计原则。

所以，在实际的软件开发中，绝大部分情况下，朴素的字符串匹配算法就够用了。

RK 算法

RK 算法的全称叫 Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的。

RK 算法其实就是上面 BF 算法的升级版。

RK 算法的思路是这样的：

• 我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小
• 如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（这里先不考虑哈希冲突的问题）
• 因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了

哈希算法的设计

不过，通过哈希算法计算子串的哈希值的时候，我们需要遍历子串中的每个字符。尽管模式串与子串比较的效率提高了，但是，算法整体的效率并没有提高。有没有方法可以提高哈希算法计算子串哈希值的效率呢？

这就需要哈希算法设计的非常有技巧了。我们假设要匹配的字符串的字符集中只包含 K 个字符，我们可以用一个 K 进制数来表示一个子串，将这个 K 进制数转化成十进制数，作为子串的哈希值。

比如假设要处理的字符串只包含 a～z 这 26 个小写字母，那就用二十六进制来表示一个字符串。我们把 a～z 这 26 个字符映射到 0～25 这 26 个数字，a 就表示 0，b 就表示 1，以此类推，z 表示 25。

在十进制的表示法中，一个数字的值是通过下面的方式计算出来的。对应到二十六进制，一个包含 a 到 z 这 26 个字符的字符串，计算哈希的时候，我们只需要把进位从 10 改成 26 即可。

哈希算法的规律

这种哈希算法有一个特点，在主串中，相邻两个子串的哈希值的计算公式有一定关系。

假设 i 表示子串在主串中的起始位置，子串的长度为 m

规律：相邻两个子串 s[i-1] 和 s[i]，对应的哈希值计算公式有交集，也就是说，我们可以使用 s[i-1] 的哈希值很快的计算出 s[i] 的哈希值。

注意：下图中最后一行少了一个左括号

只要当子串的长度 m 很大的时候才有意义

另外，26^(m-1) 这部分的计算，我们可以通过查表的方法来提高效率。我们事先计算好 26^0、261、26^2……26(m-1)，并且存储在一个长度为 m 的数组中，公式中的次方就对应数组的下标。当我们需要计算 26 的 x 次方的时候，就可以从数组的下标为 x 的位置取值，直接使用，省去了计算的时间。

时间复杂度分析

整个 RK 算法包含两部分：

• 计算子串哈希值：根据上面的分析，只需要扫描一遍主串就能计算出所有子串的哈希值了，所以时间复杂度是 O(n)
  • 注意：实际代码实现上，在扫描的过程中，一旦发现字串的哈希值和模式串的哈希值一样，就不继续计算后面字串的哈希了
• 模式串哈希值与子串哈希值之间的比较：每次比较的时间复杂度是 O(1)，总需比较 n - m + 1 次，所以时间复杂度是 O(n)

所以，RK 算法整体的时间复杂度就是 O(n)。

引入散列冲突

这里还有一个问题：如果模式串很长，相应的主串中的子串也会很长，通过上面的哈希算法计算得到的哈希值就可能很大，如果超过了计算机中整型数据可以表示的范围，那该如何解决呢？

上面设计的哈希算法是没有散列冲突的，也就是说，一个字符串与一个二十六进制数一一对应，不同的字符串的哈希值肯定不一样的。

而为了能将哈希值落在整型数据范围内，就必须允许哈希冲突（鸽巢原理）。这个时候哈希算法该如何设计呢？

哈希算法的设计方法有很多

• 比如可以把字符串中每个字母对应的数字相加（而不是进制），最后得到的和作为哈希值。这样哈希值的数据范围就相对要小很多了。不过，这种哈希算法的哈希冲突概率也是挺高的。
• 比如可以将每一个字母从小到大对应一个素数，而不是 1，2，3……这样的自然数，这样冲突的概率就会降低一些。

那现在新的问题来了，当存在哈希冲突的时候，有可能存在这样的情况，子串和模式串的哈希值虽然是相同的，但是两者本身并不匹配。

解决方法很简单。当我们发现一个子串的哈希值跟模式串的哈希值相等的时候，我们只需要再对比一下子串和模式串本身就好了。当然，如果子串的哈希值与模式串的哈希值不相等，那对应的子串和模式串肯定也是不匹配的，就不需要比对子串和模式串本身了。

哈希算法的冲突概率要相对控制得低一些，如果存在大量冲突，就会导致 RK 算法的时间复杂度退化，极端情况下，时间复杂度就会退化成 O(n*m)。

总结

RK 算法是借助哈希算法对 BF 算法进行改造，即对每个子串分别求哈希值，然后拿子串的哈希值与模式串的哈希值比较，减少了比较的时间。

理想情况下，RK 算法的时间复杂度是 O(n)，跟 BF 算法相比，效率提高了很多。不过这样的效率取决于哈希算法的设计方法，如果存在冲突的情况下，时间复杂度可能会退化。极端情况下，哈希算法大量冲突，时间复杂度就退化为 O(n*m)。