如何实现图解版的Boyer-Moore字符串匹配算法代码？

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

BM字符串匹配算法，一种性能优于著名kmp算法3～4倍的算法。简介如下：本章节主要分为两个部分，第一部分通过图解的方式讲解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

坏字符

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

好后缀

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

工作过程 坏字符

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

　

step1: 找到坏字符f，该字符对应模式串中位置si=5，如果当前没有找到坏字符，即完全匹配，直接返回。