漫画：如何优化 “字符串匹配算法”？

作者 |小灰来源 |程序员小灰（ID：chengxuyuanxiaohui）说起“字符串匹配”，恐怕算得上是计算机领域应用最多的功能之一，为了满足这一需求，聪明的计算机科学家们发明了...

CSDN资讯

2216人浏览 · 2020-02-19 18:25:32

CSDN资讯 · 2020-02-19 18:25:32 发布

作者 | 小灰

来源 | 程序员小灰（ID：chengxuyuanxiaohui）

说起“字符串匹配”，恐怕算得上是计算机领域应用最多的功能之一，为了满足这一需求，聪明的计算机科学家们发明了许多巧妙的算法。

在上一篇漫画中，我们介绍了BF算法和RK算法，没看过的小伙伴可以先补补课：

漫画：什么是字符串匹配算法？

今天，我们来介绍一种性能大大优化的字符串匹配算法。

BF算法是如何工作的？

正如同它的全称BruteForce一样，BF算法使用简单粗暴的方式，对主串和模式串进行逐个字符的比较。

比如给定主串和模式串如下：

它们的比较过程是什么样的呢？

第一轮，模式串和主串的第一个等长子串比较，发现第0位字符一致，第1位字符一致，第2位字符不一致：

第二轮，模式串向后挪动一位，和主串的第二个等长子串比较，发现第0位字符不一致：

第三轮，模式串继续向后挪动一位，和主串的第三个等长子串比较，发现第0位字符不一致：

以此类推，一直到第N轮：

当模式串挪动到某个合适位置，逐个字符比较，发现每一位字符都是匹配时，比较结束：

坏字符规则

“坏字符” 是什么意思？就是指模式串和子串当中不匹配的字符。

还以上面的字符串为例，当模式串和主串的第一个等长子串比较时，子串的最后一个字符T就是坏字符：

当检测到第一个坏字符之后，我们有必要让模式串一位一位向后挪动和比较吗？并不需要。

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

不难发现，模式串的第1位字符也是T，这样一来我们就可以对模式串做一次“乾坤大挪移”，直接把模式串当中的字符T和主串的坏字符对齐，进行下一轮的比较：

坏字符的位置越靠右，下一轮模式串的挪动跨度就可能越长，节省的比较次数也就越多。这就是BM算法从右向左检测的好处。

接下来，我们继续逐个字符比较，发现右侧的G、C、G都是一致的，但主串当中的字符A，是又一个坏字符：

我们按照刚才的方式，找到模式串的第2位字符也是A，于是我们把模式串的字符A和主串中的坏字符对齐，进行下一轮比较：

接下来，我们继续逐个字符比较，这次发现全部字符都是匹配的，比较公正完成：

public
static void main(String[] args) {

    String str = "GTTATAGCTGGTAGCGGCGAA";
    String pattern = "GTAGCGGCG";
    int index = boyerMoore(str, pattern);
    System.out.println("首次出现位置：" + index);
}
public static int boyerMoore(String str, String pattern) {
    int strLength = str.length();
    int patternLength = pattern.length();
    //模式串的起始位置
    int start = 0;
    while (start <= strLength - patternLength) {
        int i;
        //从后向前，逐个字符比较
        for (i = patternLength - 1; i >= 0; i--) {
            if (str.charAt(start+i) != pattern.charAt(i))
                //发现坏字符，跳出比较，i记录了坏字符的位置
                break;
        }
        if (i < 0) {
            //匹配成功，返回第一次匹配的下标位置
            return start;
        }
        //寻找坏字符在模式串中的对应
        int charIndex = findCharacter(pattern, str.charAt(start+i), i);
        //计算坏字符产生的位移
        int bcOffset = charIndex>=0 ? i-charIndex : i+1;
        start += bcOffset;
    }
    return -1;
}
//在模式串中，查找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;
}