图解Boyer-Moore算法的原理是怎样的？

本文共计2613个文字，预计阅读时间需要11分钟。

BM字符串匹配算法，一种性能优于著名kmp算法3-4倍的算法。简介：本文主要分为两部分，第一部分通过图解方式讲解BM算法，第二部分则通过代码实现一个简单的BM算法。基本原理：BM算法利用一些启发式策略，如坏字符规则和好后缀规则，来减少比较次数，从而提高字符串匹配的效率。

BM字符串匹配算法，一个性能优于著名kmp算法3～4倍的算法。

简介

本篇文章主要分为两个大的部分，第一部分通过图解的方式讲解BM算法，第二部分则代码实现一个简易的BM算法。

基本概念

bm是一个字符串匹配算法，有实验统计，该算法是著名kmp算法性能的3～4倍，其中有两个关键概念，坏字符和好后缀。

首先举一个例子

需要进行匹配的主串：a b c a g f a c j k a c k e a c

匹配的模式串：a c k e a c

坏字符

如下图所示，从模式串最后一个字符开始匹配，主串中第一个出现的不匹配的字符叫做坏字符。

好后缀

如下图所示，从模式串最后一个字符开始匹配，匹配到的主串中的字符为好后缀。

工作过程 坏字符

依旧是这张图，接下来我们按从简单情况到复杂情况进行分析。