簡(jiǎn)介

本篇文章主要分為兩個(gè)大的部分，第一部分通過(guò)圖解的方式講解BM算法，第二部分則代碼實(shí)現(xiàn)一個(gè)簡(jiǎn)易的BM算法。

基本概念

bm是一個(gè)字符串匹配算法，有實(shí)驗(yàn)統(tǒng)計(jì)，該算法是著名kmp算法性能的3～4倍，其中有兩個(gè)關(guān)鍵概念，壞字符和好后綴。

首先舉一個(gè)例子

需要進(jìn)行匹配的主串：a b c a g f a c j k a c k e a c

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

壞字符

如下圖所示，從模式串最后一個(gè)字符開(kāi)始匹配，主串中第一個(gè)出現(xiàn)的不匹配的字符叫做壞字符。

好后綴

如下圖所示，從模式串最后一個(gè)字符開(kāi)始匹配，匹配到的主串中的字符為好后綴。

工作過(guò)程

壞字符

依舊是這張圖，接下來(lái)我們按從簡(jiǎn)單情況到復(fù)雜情況進(jìn)行分析。

step1: 找到壞字符f，該字符對(duì)應(yīng)模式串中位置si=5，如果當(dāng)前沒(méi)有找到壞字符，即完全匹配，直接返回。

step2: 查找字符f在模式串中出現(xiàn)位置，在當(dāng)前模式串中，f沒(méi)有出現(xiàn)，證明之前沒(méi)有情況可以匹配，模式串直接滑到f后面位置。此次結(jié)束，否則step3。

step3: 舉個(gè)例子吧，如果主串和模式串如下，f為壞字符，模式串中存在f，記位置xi=3，這時(shí)候不能直接滑到f的后面，這時(shí)候應(yīng)該將模式串中的f和主串中的f對(duì)齊，如果是下面這個(gè)例子，此時(shí)直接匹配成功。如果模式串中不止存在一個(gè)f我們?nèi)绾芜x擇呢？用哪個(gè)f與模式串f對(duì)齊？答案是模式串中靠后的，如果使用靠前的，可能會(huì)多滑。

在壞字符匹配方法中，模式串往后滑動(dòng)的距離應(yīng)該是si-xi（如果壞字符在模式串中不存在，xi=-1）。

但是壞字符方法可能存在一個(gè)問(wèn)題，看下面這個(gè)例子，壞字符a，對(duì)應(yīng)匹配串中位置si=0，但是在匹配串中靠后出現(xiàn)位置xi=2，si-xi=-2，匹配串還往前移動(dòng)，這樣就會(huì)出現(xiàn)問(wèn)題，但是當(dāng)我們把下面的好后綴講了之后，這個(gè)問(wèn)題就迎刃而解了。

好后綴

首先看這張圖，這時(shí)候我們暫時(shí)不管壞字符方法（壞字符為k），由簡(jiǎn)單情況到復(fù)雜情況進(jìn)行分析。

step1：找到好后綴ac，起始位置si=4

step2：在模式串中查找其他位置是否存在好后綴ac（如果存在多個(gè)，為了不過(guò)度滑動(dòng)，仍然選擇靠后的一個(gè)），找到開(kāi)頭的ac，起始位置xi=0，滑動(dòng)模式串使得找到的開(kāi)頭ac與好后綴ac匹配，滑動(dòng)距離si-xi=4。此次結(jié)束，否則step3。

step3：還是先舉個(gè)例子，假設(shè)模式串如下圖所示，此時(shí)好后綴為ac，但是在整個(gè)模式串其他地方不存在ac，此時(shí)如果我們直接將模式串滑到ac之后，則會(huì)出現(xiàn)問(wèn)題，實(shí)際上我們只需要滑到c的位置即可。一般化的場(chǎng)景我們需要怎么操作呢？對(duì)于好后綴，如果匹配串的前綴能夠和好后綴的后綴匹配上，則我們直接滑到匹配位置。計(jì)算方式：好后綴后綴起始位置-0。

思考一下：如果匹配串中間出現(xiàn)與好后綴后綴匹配的情況，是否需要考慮？答案是否定的，當(dāng)中間出現(xiàn)的時(shí)候，滑動(dòng)過(guò)去肯定匹配不上。

BM算法

說(shuō)完了BM算法中的兩個(gè)重要概念之后，BM算法具體怎樣實(shí)現(xiàn)的呢？

其實(shí)BM算法就是壞字符和好后綴的結(jié)合，具體就是匹配串向前滑動(dòng)距離取兩者計(jì)算出來(lái)的較大值。

具體步驟我們用圖來(lái)演示一遍

代碼實(shí)現(xiàn)

在上面，我們說(shuō)到了，在BM算法中有兩個(gè)關(guān)鍵概念--壞字符和好后綴，所以我們的代碼實(shí)現(xiàn)將分為三個(gè)步驟。

• 利用壞字符算法，計(jì)算匹配串可以滑動(dòng)的距離
• 利用好后綴算法，計(jì)算匹配串可以滑動(dòng)的距離
• 結(jié)合壞字符算法和好后綴算法，實(shí)現(xiàn)BM算法，查看匹配串在主串中存在的位置

step1: 壞字符算法，經(jīng)過(guò)之前的分析，我們找到壞字符之后，需要查找匹配串中是否出現(xiàn)過(guò)壞字符，如果出現(xiàn)多個(gè)，我們滑動(dòng)匹配串，將靠后的壞字符與主串壞字符對(duì)齊。如果不存在，則完全匹配。如果我們每次找到壞字符都去查找一次匹配串中是否出現(xiàn)過(guò)，效率不高，所以我們可以用一個(gè)hash表保存匹配串中出現(xiàn)的字符以及最后出現(xiàn)的位置，提高查找效率。 

我們?cè)O(shè)定的只有小寫(xiě)字母，可以直接利用一個(gè)26大小的數(shù)組存儲(chǔ)，數(shù)組下標(biāo)存儲(chǔ)出現(xiàn)的字符（字符-‘a’），數(shù)組值存儲(chǔ)出現(xiàn)的位置?！　?/p>

int[] modelStrIndex;
    private void badCharInit(char[] modelStr) {
        modelStrIndex = new int[26];
        //-1表示該字符在匹配串中沒(méi)有出現(xiàn)過(guò)
        for (int i = 0 ; i < 26 ; i ++) {
            modelStrIndex[i] = -1;
        }
        for (int i = 0 ; i < modelStr.length ; i++) {
            //直接依次存入，出現(xiàn)相同的直接覆蓋，
            //保證保存的時(shí)候靠后出現(xiàn)的位置
            modelStrIndex[modelStr[i] - 'a'] = i;
        }
    }

查找壞字符出現(xiàn)位置badCharIndex，未出現(xiàn)，匹配成功，直接返回0。

查找匹配串中出現(xiàn)的壞字符位置modelStrIndex，未出現(xiàn)，滑動(dòng)到壞字符位置之后，直接返回匹配串的長(zhǎng)度。

返回badCharIndex - modelStrIndex。

注：壞字符是指與匹配串字符不匹配的主串字符，是看的主串，但是我們計(jì)算的位置，是匹配串中的位置。

/**
     * @param mainStr 主串
     * @param modelStr 模式串
     * @param start 模式串在主串中的起始位置
     * @return 模式串可滑動(dòng)距離，如果為0則匹配上
     */
    private int badChar(char[] mainStr, char[] modelStr, int start) {
        //壞字符位置
        int badCharIndex = -1;
        char badChar = '\0';
        //開(kāi)始從匹配串后往前進(jìn)行匹配
        for (int i = modelStr.length - 1 ; i >= 0 ; i --) {
            int mainStrIndex = start + i;
            //第一個(gè)出現(xiàn)不匹配的即為壞字符
            if (mainStr[mainStrIndex] != modelStr[i]) {
                badCharIndex = i;
                badChar = mainStr[mainStrIndex];
                break;
            }
        }
        if (-1 == badCharIndex) {
            //不存在壞字符,需匹配成功，要移動(dòng)距離為0
            return 0;
        }
        //查看壞字符在匹配串中出現(xiàn)的位置
        if (modelStrIndex[badChar - 'a'] > -1) {
            //出現(xiàn)過(guò)
            return badCharIndex - modelStrIndex[badChar - 'a'];
        }
        return modelStr.length;
    }

step2:好后綴算法，經(jīng)過(guò)之前的分析，我們?cè)趯?shí)現(xiàn)好后綴算法的時(shí)候，有一個(gè)后綴前綴匹配的過(guò)程，這里我們?nèi)匀豢梢允孪冗M(jìn)行處理。將匹配串一分為二，分別匹配前綴和后綴字串。ps：開(kāi)始我的處理是兩個(gè)數(shù)組，將前綴后綴存下來(lái)，需要的時(shí)候進(jìn)行匹配，但是在寫(xiě)文章的時(shí)候，我突然回過(guò)神來(lái)，我已經(jīng)處理了一遍了，為什么不直接標(biāo)記是否匹配呢？

初始化匹配串前綴后綴是否匹配數(shù)組，標(biāo)志當(dāng)前長(zhǎng)度的前綴后綴是否匹配。

//對(duì)應(yīng)位置的前綴后綴是否匹配
    boolean[] isMatch;
    public void goodSuffixInit(char[] modelStr) {
        isMatch = new boolean[modelStr.length / 2];
        StringBuilder prefixStr = new StringBuilder();
        List<Character> suffixChar = new ArrayList<>(modelStr.length / 2);
        for (int i = 0 ; i < modelStr.length / 2 ; i ++) {
            prefixStr.append(modelStr[i]);
            suffixChar.add(0, modelStr[modelStr.length - i - 1]);
            isMatch[i] = this.madeSuffix(suffixChar).equals(prefixStr.toString());
        }
    }
    /**
     * 組裝后綴數(shù)據(jù)
     * @param characters
     * @return
     */
    private String madeSuffix(List<Character> characters) {
        StringBuilder sb = new StringBuilder();
        for (Character ch : characters) {
            sb.append(ch);
        }
        return sb.toString();
    }

step3: 結(jié)合壞字符和好后綴算法實(shí)現(xiàn)BM算法，起始就是每一次匹配，同時(shí)調(diào)用壞字符和好后綴算法，如果返回移動(dòng)距離為0，表示已經(jīng)匹配成功，直接返回當(dāng)前匹配的起始距離。其余情況下，滑動(dòng)壞字符和好后綴算法返回的較大值。如果主串匹配完還沒(méi)有匹配成功，則返回-1。

注：加了一些日志打印匹配過(guò)程

public int bmStrMatch(char[] mainStr, char[] modelStr) {
        //初始化壞字符和好后綴需要的數(shù)據(jù)
        this.badCharInit(modelStr);
        this.goodSuffixInit(modelStr);
    int start = 0;
        while (start + modelStr.length <= mainStr.length) {
            //壞字符計(jì)算的需要滑動(dòng)的距離
            int badDistance = this.badChar(mainStr, modelStr, start);
            //好后綴計(jì)算的需要滑動(dòng)的距離
            int goodSuffixDistance = this.goodSuffix(mainStr, modelStr, start);
            System.out.println("badDistance = " +badDistance  + "， goodSuffixDistance = " + goodSuffixDistance);
            //任意一個(gè)匹配成功即成功（可以計(jì)算了壞字符和好后綴之后分別判斷一下）
            //減少一次操作
            if (0 == badDistance || 0 == goodSuffixDistance) {
                System.out.println("匹配到的位置 ：" + start);
                return start;
            }
            start += Math.max(badDistance, goodSuffixDistance);
            System.out.println("滑動(dòng)至：" + start);
        }
        return -1;
    }

最后

使用前面使用的例子，我們來(lái)實(shí)際調(diào)用一下

public static void main(String[] args) {
        BoyerMoore moore = new BoyerMoore();
        char[] mainStr = new char[]{'a','b', 'c', 'a', 'g', 'f', 'a', 'c', 'j', 'k', 'a', 'c', 'k', 'e', 'a', 'c'};
        char[] modelStr = new char[]{'a', 'c', 'k', 'e', 'a', 'c'};
        System.out.println(moore.bmStrMatch(mainStr, modelStr));
    }

調(diào)用結(jié)果

以上就是Java中BM(Boyer-Moore)算法的圖解與實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于Java BM算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！