Loading... 字符串匹配的算法有很多,本篇文章主要介绍两种比较简单的算法:BF算法和RK算法。 ## 准备 在开始讲解算法之前,我们先了解两个概念:**主串**和**模式串**。这俩概念很好理解,我举个例子你就懂了: > 我们在字符串 A 中查找字符串 B,那字符串 A 就是主串,字符串 B 就是模式串。 ## BF算法 BF 算法的全称为 Brute Force 算法,中文叫做暴力匹配算法,也叫朴素匹配算法。顾名思义,这个算法简单暴力。但同样的,算法效率也不是很高。 ### 算法思想 既然是简单暴力的算法,BF算法的思想也可以用一句话概括:**在主串中,依次遍历起始位置为0,1,2,……,n - m 且长度为 m 的 n - m + 1 个子串,看是否有和模式串相同的子串。(其中 n 为主串的长度,m 为模式串的长度)** ### 代码实现 这里放一份我顺手写的代码吧(仅供参考): ```cpp /** * \brief BF算法 * \param main_string 主串 * \param pattern_string 模式串 * \return 主串中是否存在模式串 */ int BF_find(const string& main_string, const string& pattern_string) { const int len = main_string.length() - pattern_string.length(); for (auto i = 0; i <= len; i++) { // 找到和模式串第一个字符相同的 if (main_string[i] == pattern_string[0]) { bool same = true; // 判断剩下的是否相同 for (auto j = 0; j < pattern_string.length(); j++) { if (main_string[i + j] != pattern_string[j]) { same = false; break; } } // 相同则返回偏移量 if (same) return i; } } return -1; } ``` 可以很容易看出:在极端情况下,比如在 aaa……aaaa 这样一个字符串中匹配 aaab 这样的字符串,我们就需要匹配 n - m + 1 次,每次匹配 m 个字符。所以该算法的最坏时间复杂度就是 O(m\*n)。 ## RK算法 RK算法全称叫做 Rabin-Karp算法。是由 Rabin 和 Karp 共同提出的一个算法。 RK算法是对BF算法的一个改进:在BF算法中,每一个字符都需要进行比较,并且当我们发现首字符匹配时仍然需要比较剩余的所有字符。而在RK算法中,就尝试只进行一次比较来判定两者是否相等。 那么它是如何做到一次比较就判断相等呢?让我们来看看它是怎么做的: ### 算法思想 BF算法在检查子串和模板串是否相同的时候是逐字符比对的,这就导致了它的时间复杂度比较高。但如果我们稍微改造一下对比的方法,引入哈希算法,复杂度就会降低许多。 所以RK算法的思路如下:**将模式串的 hash 值跟主串中的每一个长度为 m 的子串的 hash 值比较。如果不同,则它们肯定不相等;如果相同,由于哈希冲突存在,再逐字符的比较。** 因为哈希后是一个数字,数字之间的比较是非常快的,所以模式串和子串的比较就快了很多。 不过虽然模式串和子串的比较变快了,但是计算哈希需要遍历子串,所以整体时间复杂度似乎还是不变。这个如何解决呢? 这就需要哈希函数设计的有技巧了。我们可以假设我们要匹配的字符串只包含 K 个字符,那么我们就可以将其转化为一个 K 进制数,然后转化为十进制作为子串的哈希值。 举个小例子:假设我们要处理的的字符串只包含 a-z 这 26 个小写字母,那我们就用26进制来表示这个字符串。a 表示 0,b 表示 1,以此类推。 > 比如字符串 "cba" 进行运算的过程为: > "cba" = 'c' * 26 * 26 + 'b' * 26 + 'a' > = 2 * 26 * 26 + 1 * 26 + 0 > = 1353 ### 时间复杂度 上面说 RK 算法比 BF 算法更快,那我们就来分析一下 RK算法的时间复杂度吧: - 计算哈希值可以通过一些方法,比如查表,快速的算出哈希值,复杂度约为 O(n) - 模式串和子串哈希值比较的时间复杂度为 O(1) - 总共需比较 n - m + 1 次 所以整体的时间复杂度大约为 O(n)。 ### 数据溢出 我们刚才使用的 K 进制的方法是没有散列冲突的。但是有一个问题,如果字符串过长,很可能超过计算机中整型数据的最大值的。这里哦我们可以通过允许一些散列冲突,让转换后的数可以存在整型数据中。 > 比如不将字符串当成一个 K 进制数,而是将每个字符转换为整型数后再相加。当然方法不止这一种,这个方法只是举例。 ### 散列冲突 那么新的问题来了,上面说了我们会有一些散列冲突的情况发生,所以我们需要判定是不是散列冲突的情况。 这种其实很好判断。只需要再将子串和模式串逐字节比较一下就好了。因为哈希值不一样的一定不相等,所以还是可以提高一些效率的。 ### 代码实现 随便写的参考代码,有问题请大佬指正: ```cpp /** * \brief RK算法 * \param main_string 主串 * \param pattern_string 模式串 * \return 模式串在主串中的偏移量 */ int RK_find(const string& main_string, const string& pattern_string) { const int len = main_string.length() - pattern_string.length(); int refer = 0; // 模式串的哈希值 // 使用字符的 ASCII 码之和当作哈希 for (auto& i : pattern_string) refer += static_cast<int>(i); for (auto i = 0; i <= len; i++) { int cmp = 0; // 子串的 hash 值 for (auto j = 0; j < pattern_string.length(); j++) cmp += static_cast<int>(main_string[i + j]); // 如果哈希值相同,则判断是否为散列冲突 if (cmp == refer) { bool same = true; for (auto j = 0; j < pattern_string.length(); j++) { if (main_string[i + j] != pattern_string[j]) { same = false; break; } } // 相同则返回偏移值 if (same) return i; } } return -1; } ``` 最后修改:2019 年 10 月 17 日 © 允许规范转载 赞 如果觉得我的文章对你有用,请随意赞赏