单模式匹配算法，也就是一个字符串和另一个字符串进行匹配。
1. BF 算法
BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也加朴素匹配算法。从名字可以看出，这种方法很暴力，效率也不高，但是简单、好懂。
在要匹配的两个字符串中，一个称之为主串，一个称之为模式串。比如要在字符串中 A 中查找字符串 B，那么字符串 A 就是主串，字符串 B 就是模式串。子串的长度为 n，模式串的长度为 m，因为要在主串中查找模式串，所以有 n>m。
BF 算法的思想很简单，就是拿主串中起始位置分别为 长度为 m 的总共 n-m+1 个子串分别与模式串进行比较，看有没有能匹配上的。
可以看到，每次我们都要比较 m 个字符，极端情况下总共要比较 n-m+1 次，所以算法的最坏情况时间复杂度为 O(m*n)。
可以看到，这个算法的时间复杂度很高，但在实际的开发中，它却是一个比较常用的字符串匹配算法。一者因为实际开发中两个字符串的长度都不会太长，而且也不会每次都需要比较 n-m+1 次；二者因为其算法实现起来非常简单，不容易出错，便于维护。这也就是我们常说的 KISS(Keep it Simple and Stupid) 原则。
2. RK 算法
RK 算法的全称叫作 Rabin-Karp 算法，是为了纪念它的两个发明者而这样命名的。 这个算法其实就是刚刚 BF 算法的升级版。
在 BF 算法中，每次都要对 m 个字符逐个进行比较，这就大大降低了算法的效率。这时候，我们引入哈希算法，对子串逐个求哈希值，然后与模式串的哈希值进行比较来判断两个子串是否匹配。在不考虑哈希冲突的情况下，数字之间的比较就非常快了。
但是，在计算子串哈希值的时候，我们依然需要遍历 m 个字符，算法整体的效率并没有提高。我们需要设计一个特殊的哈希函数来避免每次都要遍历 m 个字符，这样，算法的效率就会大大改善。
对此，我们将包含 K 个字符的子串用一个 K 进制数来表示，将这个 K 进制数转化为 10 进制数作为子串的哈希值。比如字符串都是由小写字母组成，那么 a-z 这 26 个字母就映射到 0-25，0 表示 a，1 表示 b，以此类推。将 K 进制的数转化为 10 进制只需要将 10 变为 K 即可，如下图所示。
这样计算哈希值的话相邻两个子串就有一定关系。
假设 、
分别是起始位置为
和
的哈希值，而
为位置为
处字符的的映射，那么就有：
其中 这个指数项可以事先计算出来放在一个数组中，当我们需要的时候，就从对应下标中取出来即可。
可以看到，计算哈希值的时候，我们只需要遍历一次主串即可计算出所有子串的哈希值，这部分时间复杂度为 O(n)。模式串和子串需要比较 n-m+1 次哈希值，这部分时间复杂度也为 O(n)。所以，RK 算法总的时间复杂度为 O(n)。
但是，如果模式串的长度很大，那么计算出来的哈希值就会超出计算机中整形数据可以表示的范围。这时候，我们就可以牺牲一下，允许出现哈希冲突，比如可以求所有字符的映射和等，这种情况下哈希值的范围就小很多了。此时，当两个子串哈希值相同时，我们需要再进一步确定二者本身是否是相同的。
获取更多精彩，请关注「seniusen」!
网友评论