字符串匹配算法

发表于

这是我参与11月更文挑战的第26天，活动详情查看：2021最后一次更文挑战

字符存储匹配算法是各种编程语言都会提供的字符匹配函数的底层依赖，它可以分为单模式匹配和多模式匹配算法。

单模式匹配：BF算法和RK算法，RK算法是BF算法的改进，它巧妙借助了哈希算法，提升了匹配的效率。

BF

  1. BF算法是Brute Force的缩写，中文译作暴力匹配算法，也叫朴素匹配算法。
  2. 两个概念：主串和模式串

如在字符串A中查找字符串B，则字符串A就是主串，字符串B就是模式串

将主串长度记为n，模式串的长度记作m。因为是在主串中查找模式串，所以n>m
3. BF算法的思想可概括为：在主串中，检查起始位置分别是0,1,2……n-m且长度为m的n-m+1个子串，看有没有更模式串匹配的。
4. 极端情况下，如主串是“aaaaa…aaaaa”，模式串是“aaaab”。每次都比对m个字符，要比对n-m+1次，所以最坏的时间复杂度是O(m*n)。
5. 虽然BF算法时间复杂度很高，但在实际开发中使用的非常常见。

原因1：实际软件开发中，大部分情况下，模式串和主串的长度都不会太长。每次模式串与主串中的子串匹配时，当中途不能遇到匹配的字符的时候，就可以停止，不需要全部对比一次。所以理论上最坏情况时间复杂度是O(m*n)，但这更多的是统计意义上的，大部分情况中，这个算法执行的很高效。

原因2：朴素字符串匹配算法思想简单，代码实现也非常简单，简单就意味着不容易出错。工程中，在满足性能要求的前提下，简单是首选，也是常说的KISS（keep it Simple and Stupid）设计原则。

RK

  1. RK算法的全称是Rabin-Karp算法，是两位发明人的名字拼接。是BF算法的升级版
  2. BF算法的问题在于每次检查主串与子串是否匹配，需要依次对比每个字符，所以BF算法的时间复杂就比较高。但引入哈希算法，时间复杂度立即就会降低。
  3. RK算法的思路：

通过哈希算法对主串中的n-m+1个子串分别求哈希值，

然后逐个于模式串的哈希值比较大小，如果相等就说明有对应的模式串。
4. 通过哈希算法计算字符的哈希值时，需要遍历子串中的每个字符，这只提供了模式串与子串比较的效率，但整体的效率并没有提高。
5. 为了提高哈希算法计算子串哈希值的效率，可以通过哈希算法的设计来解决。

假设要匹配的字符串的字符集中只包含k个字符，这就可以用一个k进制数来表示一个子串，这个k进制数转化成十进制，作为子串的哈希值。

  1. 这种哈希算法有个特点，在主串中，相邻两个子串的哈希值的计算公式有一定关系。
  2. RK算法的时间复杂度：
1. 整个RK算法包含两个部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。
2. 第一部分，只需要扫描一遍主串就能计算出所有子串的哈希值了，复杂度是O(n)。
3. 模式串哈希值与每个子串哈希值之间的比较时间复杂度是O(1)，总共需要比较n-m+1个子串的哈希值，所有，这部分的时间复杂度也是O(n)。所以RK算法整体时间复杂度就是`O(n)`。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%