作者 | 小灰
本文经授权转载自程序员小灰（ID：chengxuyuanxiaohui）
说起“字符串匹配”，恐怕算得上是计算机领域应用最多的功能之一，为了满足这一需求，聪明的计算机科学家们发明了许多巧妙的算法。
所以，今天，我们来介绍一种性能大大优化的字符串匹配算法。
BF算法是如何工作的？
正如同它的全称BruteForce一样，BF算法使用简单粗暴的方式，对主串和模式串进行逐个字符的比较。
比如给定主串和模式串如下：
它们的比较过程是什么样的呢？
第一轮，模式串和主串的第一个等长子串比较，发现第0位字符一致，第1位字符一致，第2位字符不一致：
第二轮，模式串向后挪动一位，和主串的第二个等长子串比较，发现第0位字符不一致：
第三轮，模式串继续向后挪动一位，和主串的第三个等长子串比较，发现第0位字符不一致：
以此类推，一直到第N轮：
当模式串挪动到某个合适位置，逐个字符比较，发现每一位字符都是匹配时，比较结束：
坏字符规则
“坏字符” 是什么意思？就是指模式串和子串当中不匹配的字符。
还以上面的字符串为例，当模式串和主串的第一个等长子串比较时，子串的最后一个字符T就是坏字符：
当检测到第一个坏字符之后，我们有必要让模式串一位一位向后挪动和比较吗？并不需要。
因为只有模式串与坏字符T对齐的位置也是字符T的情况下，两者才有匹配的可能。
不难发现，模式串的第1位字符也是T，这样一来我们就可以对模式串做一次“乾坤大挪移”，直接把模式串当中的字符T和主串的坏字符对齐，进行下一轮的比较：
坏字符的位置越靠右，下一轮模式串的挪动跨度就可能越长，节省的比较次数也就越多。这就是BM算法从右向左检测的好处。
接下来，我们继续逐个字符比较，发现右侧的G、C、G都是一致的，但主串当中的字符A，是又一个坏字符：
我们按照刚才的方式，找到模式串的第2位字符也是A，于是我们把模式串的字符A和主串中的坏字符对齐，进行下一轮比较：
接下来，我们继续逐个字符比较，这次发现全部字符都是匹配的，比较公正完成：
//在模式串中，查找index下标之前的字符是否和坏字符匹配
private static int findCharacter(String pattern, char badCharacter, int index) {
for(int i= index-1; i>=0; i--){
if(pattern.charAt(i) == badCharacter){
return i;
}
}
//模式串不存在该字符，返回-1
return -1;
}
public static int boyerMoore(String str, String pattern) {
int strLength = str.length();
int patternLength = pattern.length();
//模式串的起始位置
int start = 0;
while (start = 0; i--) {
if (str.charAt(start+i) != pattern.charAt(i))
//发现坏字符，跳出比较，i记录了坏字符的位置
break;
}
if (i =0 ? i-charIndex : i+1;
start += bcOffset;
}
return -1;
}
public static void main(String[] args) {
String str = "GTTATAGCTGGTAGCGGCGAA";
String pattern = "GTAGCGGCG";
int index = boyerMoore(str, pattern);
System.out.println("首次出现位置：" + index);
}
好后缀规则
“好后缀” 又是什么意思？就是指模式串和子串当中相匹配的后缀。
让我们看一组新的例子：
对于上面的例子，如何我们继续使用“坏字符规则”，会有怎样的效果呢？
从后向前比对字符，我们发现后面三个字符都是匹配的，到了第四个字符的时候，发现坏字符G：
接下来我们在模式串找到了对应的字符G，但是按照坏字符规则，模式串仅仅能够向后挪动一位：
这时候坏字符规则显然并没有起到作用，为了能真正减少比较次数，轮到我们的好后缀规则出场了。由于好后缀规则的实现细节比坏字符规则要难理解得多，所以我们这里只介绍一个大概思路：
我们回到第一轮的比较过程，发现主串和模式串都有共同的后缀“GCG”，这就是所谓的“好后缀”。
如果模式串其他位置也包含与“GCG”相同的片段，那么我们就可以挪动模式串，让这个片段和好后缀对齐，进行下一轮的比较：
显然，在这个例子中，采用好后缀规则能够让模式串向后移动更多位，节省了更多无谓的比较。
CSDNx巨杉大学联合认证学习，免费开放！
“分布式数据库集训营”帮助您从零开始学习分布式数据库、分布式架构知识，现在加入活动，完成课程还将专属礼品。快来参加吧！
了解详情请戳：http://www.sequoiadb.com/cn/university-camp
热 文 推 荐
☞隐身术？登顶 GitHub Top1：200 行 JS 代码让画面人物瞬间消失！ ☞“不让一块芯片流向华为”？ ☞稳定、可扩展、模块化、简化部署过程、版本控制……一文看懂 Kubernetes 到底如何运用！ ☞为什么 Kafka 这么快？ ☞我们需要什么样的数据架构？ ☞男性玩家占78.8%、90后玩家占近50%、最多人选择中国风链游……《2019链游玩家需求调研报告》重磅发布！你点的每个“在看”，我都认真当成了喜欢
