算法：字符串匹配算法：BM算法

拼搏现实的明天。 2023-07-10 08:44 9阅读 0赞

![在这里插入图片描述][20200301170853687.png]  
![在这里插入图片描述][20200301171008841.png]  
![在这里插入图片描述][20200301171027938.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][2020030117112361.png]  
当检测到第一个坏字符之后，我们有必要让模式串一位一位向后挪动和比较吗？并不需要。

因为只有模式串与坏字符T对齐的位置也是字符T的情况下，两者才有匹配的可能。

不难发现，模式串的第1位字符也是T，这样一来我们就可以对模式串做一次“乾坤大挪移”，直接把模式串当中的字符T和主串的坏字符对齐，进行下一轮的比较：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][20200301171318129.png]  
![在这里插入图片描述][20200301171352539.png]  
![在这里插入图片描述][20200301171411232.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 3]  
只有坏规则条件下的代码：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 4]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 7]

![在这里插入图片描述][20200301171732135.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 9]  
![在这里插入图片描述][20200301171832826.png]  
![在这里插入图片描述][20200301171908397.png]

[20200301170853687.png]: https://img-blog.csdnimg.cn/20200301170853687.png
[20200301171008841.png]: https://img-blog.csdnimg.cn/20200301171008841.png
[20200301171027938.png]: https://img-blog.csdnimg.cn/20200301171027938.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200301171100931.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[2020030117112361.png]: https://img-blog.csdnimg.cn/2020030117112361.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200301171219910.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200301171257507.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[20200301171318129.png]: https://img-blog.csdnimg.cn/20200301171318129.png
[20200301171352539.png]: https://img-blog.csdnimg.cn/20200301171352539.png
[20200301171411232.png]: https://img-blog.csdnimg.cn/20200301171411232.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200301171428200.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200301172051825.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/2020030117151157.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200301171627411.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200301171717301.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[20200301171732135.png]: https://img-blog.csdnimg.cn/20200301171732135.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200301171755991.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200301171817545.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[20200301171832826.png]: https://img-blog.csdnimg.cn/20200301171832826.png
[20200301171908397.png]: https://img-blog.csdnimg.cn/20200301171908397.png