【数据结构与算法】字符串匹配 BF算法 RK算法

小咪咪 2022-11-30 12:56 189阅读 0赞

1.  单模式串匹配  
    **BF 算法和 RK 算法**  
    BM 算法和 KMP 算法
2.  多模式串匹配算法  
    Trie 树和 AC 自动机

### 一、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）设计原则。  
6。应用 Java IndexOf  
处理小规模的字符串匹配

### 二、RK算法： ###

![加粗样式][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

1，RK算法的全称是Rabin-Karp算法，是两位发明人的名字拼接。是BF算法的升级版  
2，BF算法的问题在于每次检查主串与子串是否匹配，需要依次对比每个字符，所以BF算法的时间复杂就比较高。但引入**哈希算法**，时间复杂度立即就会降低。  
3，RK算法的思路：  
通过哈希算法对主串中的n-m+1个子串分别求哈希值，  
然后逐个于模式串的哈希值比较大小，如果相等就说明有对应的模式串。  
4，通过哈希算法计算字符的哈希值时，需要遍历子串中的每个字符，这只提供了模式串与子串比较的效率，但整体的效率并没有提高。  
5，为了提高哈希算法计算子串哈希值的效率，可以通过哈希算法的设计来解决。  
假设要匹配的字符串的字符集中只包含k个字符，这就可以用一个k进制数来表示一个子串，这个k进制数转化成k  
进制，作为子串的哈希值。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

6，这种哈希算法有个特点，在主串中，相邻两个子串的哈希值的计算公式有一定关系。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]

7，RK算法的时间复杂度：  
①：整个RK算法包含两个部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。  
②：第一部分，只需要扫描一遍主串就能计算出所有子串的哈希值了，复杂度是**O(n)**。  
③：模式串哈希值与每个子串哈希值之间的比较时间复杂度是O(1)，总共需要比较n-m+1个子串的哈希值，所有，这部分的时间复杂度也是O(n)。  
所以RK算法整体时间复杂度就是O(n)。

8，如果模式串很长，相应的主串中子串也会很长，通过上面的哈希算法计算得到的哈希值就可能很大，如果超过了计算机中整形数据可以表示范围，该如何解决？  
答：我们可以把字符串中每个字母的数字相加(每个字母代表一个素数)，最后得到的和作为哈希值。这种哈希算法产生的哈希值的数据范围就相对要小很多。  
9，若出现哈希冲突如何解决？  
答：如果两值相等，比较子串中每个字符。

所以，哈希算法中的冲突概率要相对控制得低一些，如果存在大量冲突，就会导致RK算法的时间复杂度退化，效率下降。极端情况下，如果存在大量的冲突，每次都要对比子串和模式串本身，时间复杂度就会退化成O(n\*m)。

[笔记整理来源： 王争 数据结构与算法之美][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/aa10310e3a71456aada72a69b7c3ad7a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/6bb7fd609bd74706a9a1629f828936d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/9d53c73c1c434c3dbfafc11c6dae2a3d.png
[Link 1]: https://s1.ax1x.com/2020/08/03/aUh2TS.png