字符串匹配基础(上)
BF 算法和 RK 算法
BF 算法
中文叫作暴力匹配算法,也叫朴素匹配算法。
两个关键名词,主串和模式串
比方说,我们在字符串 A 中查找字符串 B,那字符串 A 就是主串,字符串 B 就是模式串。我们把主串的长度记作 n,模式串的长度记作 m。因为我们是在主串中查找模式串,所以 n>m。
BF 算法的思想可以用一句话来概括,那就是,我们在主串中,检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串,看有没有跟模式串匹配的。
时间复杂度O(n*m)
尽管时间复杂度很高,但依然是比较常用的算法,原因有两点:
- 实际的软件开发中,大部分情况下,模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候,当中途遇到不能匹配的字符的时候,就可以就停止了,不需要把 m 个字符都比对一下。所以,尽管理论上的最坏情况时间复杂度是 O(n*m),但是,统计意义上,大部分情况下,算法执行效率要比这个高很多。
- 朴素字符串匹配算法思想简单,代码实现也非常简单。简单意味着不容易出错,如果有 bug 也容易暴露和修复。在工程中,在满足性能要求的前提下,简单是首选。这也是我们常说的KISS(Keep it Simple and Stupid)设计原则。
RK 算法
设计思路:我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值,然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等,那就说明对应的子串和模式串匹配了
哈希算法设计的技巧
我们假设要匹配的字符串的字符集中只包含 K 个字符,我们可以用一个 K 进制数来表示一个子串,这个 K 进制数转化成十进制数,作为子串的哈希值。
相邻两个子串的哈希值的计算公式有一定关系
相邻两个子串 s[i-1]和 s[i](i 表示子串在主串中的起始位置,子串的长度都为 m),对应的哈希值计算公式有交集,也就是说,我们可以使用 s[i-1]的哈希值很快的计算出 s[i]的哈希值。如果用公式表示的话,就是下面这个样子:
小细节:可以事先使用一个数组保存好进制的 0~m-1 次方,这样可以节约计算时间
时间复杂度 O(n)
子串过长导致哈希值超过计算机范围时怎么办
设计一个允许哈希冲突的哈希算法,然后当哈希值相同时比较字符串内容。但注意冲突不能太多,否则会退化为O(n*m) 的算法。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!