动画：BF 和 RK 字符串匹配算法（上）

写在前边

今天这篇文章主要入门一下字符串匹配算法，说到字符串匹配，想到了实际中最常用到的方法 indexOf()，对于内部的字符串是如何进行匹配的呢，还要从数据结构和算法的角度去理解和学习。

字符串匹配算法有很多，比如，今天要分享到的 BF 和 RK 算法，以及后续要分享到的 KMP 算法、BM 算法、Sunday 算法等。说到底，这些字符串匹配算法之间都是有着密切关系滴，不同的算法效率和性能以及适用条件也是各不相同。

废话补多说，开始我们今天的字符串匹配算法之旅。

BF 算法

BF算法，又称作暴力(Brute Force)算法，是普通的模式匹配算法。

BF 算法的思想就是将子串 S 的第一个字符与模式串 T 的第一个字符进行匹配，若相等，则继续比较 S 的第二个字符和 T 的第二个字符。

若不相等，则比较 S 的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。

如果模式串是 n ，子串是 m，最坏的情况下，每次都要比较 m 个字符，最多要比较 n - m + 1 次，也就是说最坏时间复杂度为 O(n*m)

一般在应用中，太长的字符串不会使用 BF 算法来进行匹配，但是大多数的情况下， BF 算法对字符串进行匹配就够用了，即便是最坏情况下时间复杂度为 O(n*m)，综合来看，效率还算挺高的。

动画实现

RK 算法

RK 算法可以说是 BF 算法的一种优化优化。因为上述的 BF 算法存在一个很明显的缺点就是每次都要对子串和模式串一个个的比较，在最坏的情况下，非常的消耗性能，咱们能不能在比较时间上，缩短一些时间呢？

答案是能的，RK 算法就对其进行了一个优化，对比较的子串和将比较的模式串进行一个哈希计算，对（n-m+1）个子串求哈希值之後，让模式串与逐个哈希值比较。

如果提前了解过哈希算法的同学知道，哈希值就是一个数字，数字之间的比较比字符串之间的比较要快很多。

难道效率真的提高了很多吗？有同学发现了，虽然哈希算法提高了比较的效率，但是计算哈希值增加了额外的时间。那能不能更快的计算出哈希值呢？有的，但是涉及到设计哈希算法的技巧不详细在本节分享。

对于 RK 算法的性能有多高呢？首先我们先要扫描一遍字符串，计算出哈希值，时间复杂度为O(n),然后用子串的哈希值与模式串的哈希值进行比较，时间复杂度为 O(1)，一共需要比较（n-m+1）次，所以 RK 算法整体的时间复杂度为 O(n)。

小结

今天主要分享了两个最简单的字符串比较算法，尤其是对于 RK 算法里边所用的哈希算法，我们前提是在没有哈希冲突的情况下进行的，如果存在哈希冲突等一系列问题，就会导致 BF 性能效率的下降，但是哈希冲突的几率很低的。

总体来说 RK 算法还是比 BF 算法性能还是略高一筹的。

最后留一个问题就是，怎样设计哈希算法，能够提高计算哈希值的效率呢？

更多相关文章