Boyer-Moore-MagicLen(BM-MagicLen)字串搜尋演算法，超快速的全文搜尋演算法

在一篇很長的文章或是一大串文字中找出自己想看到的段落是我們時常會需要做的事情，但是要如何有效率地讓電腦尋找文字中的文字是一件需要思考的事情，甚至有許多針對這個議題所提出的研究論文。字串搜尋演算法的好壞，在複雜的文件內容下，對搜尋時間的影響是非常深遠的。字串搜尋除了能夠正確搜尋一段文字內的特定字串外，還可以用來搜尋龐大的任意資料，因為任何的資料都可以藉由數位編碼轉成只有數字的字串，如一段原始的聲音，一段原始的影片，甚至是一段生物基因。Boyer-Moore-MagicLen是筆者結合Boyer-Moore-Horspool和Quick Search Algorithm得出的演算法，這兩種都是Boyer-Moore(BM)演算法的簡化作法。

Boyer-Moore

Boyer-Moore演算法又稱BM演算法，它在開始搜尋字串之前，會先對搜尋目標，也就是樣本(pattern)進行預處理的動作，使得此演算法之後在使用這個樣本來在原文(text)中搜尋字串時，能夠利用「好後綴位移」(good-suffix shift)和「壞字元位移」(bad-character shift)，來想辦法讓目前無法與樣本相匹配的文字索引位置，能夠位移最多個字元的索引距離(若此演算法同時計算了好後綴位移和壞字元位移，則會選擇能夠位移最多的那個)，減少原文字元與樣本字元的判斷是否相同的次數，來加速字串搜尋(相對於暴力字串搜尋)。

所以什麼是「好後綴」和「壞字元」呢？如果要用口語描述的話，「好後綴」為目前位置之樣本和原文相符的字串後綴；「壞字元」為目前位置之樣本和原文從後面判斷第一個出現的不相符字元，就是好後綴開頭的前一個字元。

「好後綴位移」和「壞字元位移」的位移方式可以預先在尚未知道原文的時候，單靠樣本來建立。建立好樣本的「好後綴位移表」和「壞字元位移表」之後，無論遇到怎麼樣的原文，都可以使用這個樣本和預先處理過的表格對原文進行非常快速的字串搜尋。

以Boyer-Moore演算法的作者之一──Moore所舉的例子來說明，我們要搜尋的原文如下：

HERE IS A SIMPLE EXAMPLE

然後要搜尋的樣本為EXAMPLE。在經過預處理之後，我們已經有了「好後綴位移表」和「壞字元位移表」，因為有些複雜，這邊就先不提預處理的方式。接著進入字串搜尋階段，Boyer-Moore演算法會從原文的最前方開始，先判斷樣本的後綴是否和原文相匹配。

HERE IS A SIMPLE EXAMPLE
EXAMPLE

如上示例，可以看到原文第7個字元S和樣本第7個字元E並不相同，此時的S稱為「壞字元」，且因剛才沒有一個字元是有匹配成功的，所以此時並沒有「好後綴」。接下來Boyer-Moore演算法就會利用S這個壞字元來計算出「壞字元位移」，我們可以把此時的「壞字元位移」直接想成是要把EXAMPLE這個樣本往右移動最少幾個索引值後，樣本本身所含有的「壞字元」能和剛剛在原文中發現的「壞字元」對齊。

由於此時的「壞字元」是S，而我們也知道EXAMPLE這個樣本中並不存在「壞字元」S，所以我們不能完成「把EXAMPLE這個樣本往右移動最少幾個索引值後，樣本本身所含有的『壞字元』能和剛剛在原文中發現的『壞字元』對齊」這件事。於是此時的「壞字元位移」的策略就會變成是要把EXAMPLE這個樣本往右移動最少幾個索引值後，樣本的第1個字元會在原文的「壞字元」的下一個索引位置。並在位移之後，繼續判斷樣本的後綴是否和原文相匹配。

HERE IS A SIMPLE EXAMPLE
       EXAMPLE

如上示例，可以看到原文第14個字元P和樣本第7個字元E並不相同，此時的P稱為「壞字元」，且因剛才沒有一個字元是有匹配成功的，所以此時並沒有「好後綴」。接下來Boyer-Moore演算法就會利用P這個壞字元來計算出「壞字元位移」，使樣本在往右移動最少的索引值後，樣本本身所含有的「壞字元」能和剛剛在原文中發現的「壞字元」對齊。並在位移之後，繼續判斷樣本的後綴是否和原文相匹配。

HERE IS A SIMPLE EXAMPLE
         EXAMPLE

如上示例，可以看到原文第13個字元到第16個字元MPLE和樣本第4個字元到第7個字元是一樣的，但是原文第12個字元I和樣本第3個字元A就不相同了。此時的I稱為「壞字元」，而MPLE稱為「好後綴」。接下來Boyer-Moore演算法就會利用I這個壞字元來計算出「壞字元位移」，使樣本在往右移動多少個索引值後，樣本的第1個字元會在原文的「壞字元」的下一個索引位置，計算出來的結果會是3。而Boyer-Moore演算法也會利用MPLE這個好後綴以及PLE、LE和E這幾個延伸的好後綴來計算出「好後綴位移」，我們可以把此時的「好後綴位移」直接想成是要把EXAMPLE這個樣本往右移動最少幾個索引值後，樣本本身所含有的「好後綴」或是延伸的好後綴能和剛剛在原文中發現的「好後綴」或是延伸的好後綴對齊。

首先看有沒有辦法在樣本右移之後還能夠有MPLE能夠對齊，答案是沒有。接著看有沒有辦法在樣本右移之後還能夠有PLE能夠對齊，答案是依然沒有。再來看有沒有辦法在樣本右移之後還能夠有LE能夠對齊，還是沒有。最後發現E是可以對齊到的，需要將樣本向右移動6個索引值。

由於「壞字元位移」是3，而「好後綴位移」是6，因此Boyer-Moore演算法會選擇使用「好後綴位移」。並在位移之後，繼續判斷樣本的後綴是否和原文相匹配。

HERE IS A SIMPLE EXAMPLE
               EXAMPLE

這邊原文的P和樣本的E不同，所以Boyer-Moore演算法就會利用P這個壞字元來計算出「壞字元位移」，使樣本在往右移動最少的索引值後，樣本本身所含有的「壞字元」能和剛剛在原文中發現的「壞字元」對齊。並在位移之後，繼續判斷樣本的後綴是否和原文相匹配。

HERE IS A SIMPLE EXAMPLE
                 EXAMPLE

如此一來就成功在原文中找到樣本出現的位置了！

Boyer-Moore-Horspool

Boyer-Moore-Horspool演算法是Boyer-Moore演算法的精簡版本，它僅運用Boyer-Moore演算法的「壞字元位移」概念來完成字串的搜尋，且如果樣本匹配失敗，則永遠把正在匹配的原文範圍中的最後一個字元當作是壞字元。

重新使用以上的例子，來演示處理過程：

HERE IS A SIMPLE EXAMPLE
EXAMPLE

HERE IS A SIMPLE EXAMPLE
       EXAMPLE

HERE IS A SIMPLE EXAMPLE
         EXAMPLE

HERE IS A SIMPLE EXAMPLE
               EXAMPLE

HERE IS A SIMPLE EXAMPLE
                 EXAMPLE

以上的過程是跟Boyer-Moore演算法一樣的，但背後的演算法並不一樣。

這套演算法好像很奇怪，為什麼樣本匹配失敗時，它可以「永遠把正在匹配的原文範圍中的最後一個字元當作是壞字元」？而不是以「好後綴開頭的前一個字元」作為壞字元？這邊有個邏輯上的跳躍思考，先假設Boyer-Moore-Horspool演算法這樣的作法是正確的，我們「把正在匹配的原文範圍中的最後一個字元當作是壞字元」時，如果樣本中沒有這個字元，那麼目前涵蓋的這個範圍的原文位置肯定不會是樣本能夠匹配的位置，所以就算我們的壞字元是選擇「好後綴開頭的前一個字元」，到最後也會得到跟「把正在匹配的原文範圍中的最後一個字元當作是壞字元」時一樣的結果，也就是最終這個範圍的原文位置都會被跳過，所以倒不如一開始就直接「把正在匹配的原文範圍中的最後一個字元當作是壞字元」，會省下一些位移的次數。

那如果是「把正在匹配的原文範圍中的最後一個字元當作是壞字元」時(以下簡稱為前者)，而樣本中也有這個字元存在於其非最後一個索引位置的情況呢？如果此時我們的壞字元是選擇「好後綴開頭的前一個字元」(以下簡稱為後者)，且樣本中前面的索引位置也有這個字元的存在的話，若用後者作為壞字元所計算出來的位移量比前者還要小，可以推斷以此距離位移後，原本原文匹配範圍中的最後一個字元絕對不會與位移後樣本中對應位置的字元相同，因為我們必須要讓樣本至少經過前者作為壞字元計算出來的位移量，才能夠使原本原文匹配範圍中的最後一個字元與位移後樣本中對應位置的字元是相同的。但若用後者作為壞字元所計算出來的位移量比前者還要大時，不就也會遇到上述的問題嗎？是的，當後者作為壞字元所計算出來的位移量比前者還要大時，就會導致位移次數的增加。

舉例來說：

RPOIXYZABCDAEEFGHIJKLM
       ABCDEEE

使用Boyer-Moore演算法的話，樣本經過位移之後會變成：

RPOIXYZABCDAEEFGHIJKLM
           ABCDEEE

移動了四個索引值。

而使用Boyer-Moore-Horspool演算法的話，樣本經過位移之後會變成：

RPOIXYZABCDAEEFGHIJKLM
        ABCDEEE

只移動了一個索引值。

所以Boyer-Moore演算法和Boyer-Moore-Horspool演算法的效能是各有千秋嗎？因為剛才不是還有提到當樣本中不存在壞字元的情形時，是使用「正在匹配的原文範圍中的最後一個字元當作是壞字元」來計算位移會比較好嗎？雖然是這樣沒錯，但別忘了Boyer-Moore演算法還有一個「好後綴位移」。如果是在這個情形下，也必定不能在樣本的前段索引範圍中發現好後綴或是好後綴的延伸。所以也是一樣，不管用Boyer-Moore演算法還是Boyer-Moore-Horspool演算法，這個範圍的原文位置都會被跳過。

因此，Boyer-Moore演算法的效能理論上是比Boyer-Moore-Horspool演算法還要好一點的，不過Boyer-Moore演算法實作起來複雜很多，需要進行計算的地方很多，實際運行起來其效能也不一定總是比Boyer-Moore-Horspool演算法好。

雖然Boyer-Moore-Horspool演算法不是本篇文章的重點，不過筆者在此還是放一下Boyer-Moore-Horspool演算法的程式實作。

/// Boyer-Moore-Horspool演算法。
pub fn boyer_moore_horspool(text: &[char], pattern: &[char]) -> Vec<usize> {
    let text_len = text.len();
    let pattern_len = pattern.len();

    if text_len == 0 || pattern_len == 0 || text_len < pattern_len {
        return vec![];
    }

    let pattern_len_dec = pattern_len - 1;

    let mut bad_char_shift_map: HashMap<char, usize> = HashMap::with_capacity(pattern_len_dec);

    for (i, c) in pattern.iter().copied().take(pattern_len_dec).enumerate() {
        bad_char_shift_map.insert(c, pattern_len_dec - i);
    }

    let mut shift = 0;

    let end_index = text_len - pattern_len;

    let mut result = vec![];

    'outer: loop {
        for (i, pc) in pattern.iter().copied().enumerate().rev() {
            if text[shift + i] != pc {
                shift += bad_char_shift_map.get(&text[shift + pattern_len_dec]).copied().unwrap_or(pattern_len);
                if shift > end_index {
                    break 'outer;
                }
            }
        }
        result.push(shift);

        shift += bad_char_shift_map.get(&text[shift + pattern_len_dec]).copied().unwrap_or(pattern_len);
        if shift > end_index {
            break;
        }
    }

    result
}

/**
 * Boyer-Moore-Horspool演算法。
 */
public static Integer[] boyerMooreHorspool(final char[] text, final char[] pattern) {
    int textLength = text.length;
    int patternLength = pattern.length;

    if (textLength == 0 || patternLength == 0 || textLength < patternLength) {
        return new Integer[0];
    }

    final int patternLengthDec = patternLength - 1;

    final HashMap<Character, Integer> badCharShiftMap = new HashMap<>(patternLengthDec);

    for (int i = 0; i < patternLengthDec; ++i) {
        badCharShiftMap.put(pattern[i], patternLengthDec - i);
    }

    int shift = 0;

    final int endIndex = textLength - patternLength;

    final ArrayList<Integer> result = new ArrayList<>();

    outer:
    while (true) {
        for (int i = patternLengthDec; i >= 0; --i) {
            if (text[shift + i] != pattern[i]) {
                shift += badCharShiftMap.getOrDefault(text[shift + patternLengthDec], patternLength);
                if (shift > endIndex) {
                    break outer;
                }
            }
        }
        result.add(shift);

        shift += badCharShiftMap.getOrDefault(text[shift + patternLengthDec], patternLength);
        if (shift > endIndex) {
            break;
        }
    }

    return result.toArray(new Integer[result.size()]);
}

Quick Search Algorithm

Quick Search Algorithm與Boyer-Moore-Horspool十分相像，差別只在於Quick Search Algorithm對於壞字元的選擇策略是，在樣本匹配失敗時「永遠把正在匹配的原文範圍的下一個字元當作是壞字元」。

重新使用以上的例子，來演示處理過程：

HERE IS A SIMPLE EXAMPLE
EXAMPLE

HERE IS A SIMPLE EXAMPLE
        EXAMPLE

HERE IS A SIMPLE EXAMPLE
         EXAMPLE

HERE IS A SIMPLE EXAMPLE
                 EXAMPLE

在這個例子中，Quick Search Algorithm比Boyer-Moore-Horspool演算法和Boyer-Moore演算法都還要快。

同樣地，再拿剛剛移動索引值的例子來比較：

RPOIXYZABCDAEEFGHIJKLM
       ABCDEEE

使用Boyer-Moore演算法的話，樣本經過位移之後會變成：

RPOIXYZABCDAEEFGHIJKLM
           ABCDEEE

移動了四個索引值。

使用Boyer-Moore-Horspool演算法的話，樣本經過位移之後會變成：

RPOIXYZABCDAEEFGHIJKLM
        ABCDEEE

只移動了一個索引值。

而使用Quick Search Algorithm的話，樣本經過位移之後會變成：

RPOIXYZABCDAEEFGHIJKLM
               ABCDEEE

移動了八個索引值！

所以Quick Search Algorithm一定是最快的嗎？很可惜，若是以下的例子，就會是Boyer-Moore-Horspool演算法比較快。

RPOIXYZABCDAEEFGHIJKLM
       ABCDDFG

使用Boyer-Moore-Horspool演算法的話，樣本經過位移之後會變成：

RPOIXYZABCDAEEFGHIJKLM
              ABCDDFG

移動了七個索引值！

而使用Quick Search Algorithm的話，樣本經過位移之後會變成：

RPOIXYZABCDAEEFGHIJKLM
         ABCDDFG

只移動了兩個索引值。

也就是說，Quick Search Algorithm和Boyer-Moore-Horspool演算法的搜尋速度是互有輸贏。

雖然Quick Search Algorithm也不是本篇文章的重點，不過筆者在此還是放一下Quick Search Algorithm的程式實作。

/// Quick Search Algorithm
pub fn quick_search_algorithm(text: &[char], pattern: &[char]) -> Vec<usize> {
    let text_len = text.len();
    let pattern_len = pattern.len();

    if text_len == 0 || pattern_len == 0 || text_len < pattern_len {
        return vec![];
    }

    let pattern_len_inc = pattern_len + 1;

    let mut bad_char_shift_map: HashMap<char, usize> = HashMap::with_capacity(pattern_len);

    for (i, c) in pattern.iter().copied().enumerate() {
        bad_char_shift_map.insert(c, pattern_len - i);
    }

    let mut shift = 0;

    let end_index = text_len - pattern_len;

    let mut result = vec![];

    'outer: loop {
        for (i, pc) in pattern.iter().copied().enumerate().rev() {
            if text[shift + i] != pc {
                let p = shift + pattern_len;
                if p == text_len {
                    break 'outer;
                }
                shift += bad_char_shift_map.get(&text[p]).copied().unwrap_or(pattern_len_inc);
                if shift > end_index {
                    break 'outer;
                }
            }
        }
        result.push(shift);

        if shift == end_index {
            break;
        }

        shift += bad_char_shift_map.get(&text[shift + pattern_len]).copied().unwrap_or(pattern_len_inc);
        if shift > end_index {
            break;
        }
    }

    result
}

/**
 * Quick Search Algorithm
 */
public static Integer[] quickSearchAlgorithm(final char[] text, final char[] pattern) {
    int textLength = text.length;
    int patternLength = pattern.length;

    if (textLength == 0 || patternLength == 0 || textLength < patternLength) {
        return new Integer[0];
    }

    final int patternLengthDec = patternLength - 1;
    final int patternLengthInc = patternLength + 1;

    final HashMap<Character, Integer> badCharShiftMap = new HashMap<>(patternLength);

    for (int i = 0; i < patternLength; ++i) {
        badCharShiftMap.put(pattern[i], patternLength - i);
    }

    int shift = 0;

    final int endIndex = textLength - patternLength;

    final ArrayList<Integer> result = new ArrayList<>();

    outer:
    while (true) {
        for (int i = patternLengthDec; i >= 0; --i) {
            if (text[shift + i] != pattern[i]) {
                final int p = shift + patternLength;
                if (p == textLength) {
                    break outer;
                }
                shift += badCharShiftMap.getOrDefault(text[p], patternLengthInc);
                if (shift > endIndex) {
                    break outer;
                }
            }
        }
        result.add(shift);

        if (shift == endIndex) {
            break;
        }

        shift += badCharShiftMap.getOrDefault(text[shift + patternLength], patternLengthInc);
        if (shift > endIndex) {
            break;
        }
    }

    return result.toArray(new Integer[result.size()]);
}

Boyer-Moore-MagicLen

Boyer-Moore-MagicLen的概念

Boyer-Moore-MagicLen演算法是筆者結合Boyer-Moore-Horspool和Quick Search Algorithm的特色所想出的演算法，在樣本匹配失敗時，會「永遠把正在匹配的原文範圍的最後一個字元和下一個字元當作是壞字元」，所以可以求得兩個壞字元位移，再仿效Boyer-Moore演算法選擇壞字元位移和好後綴位移之最大值的方式，Boyer-Moore-MagicLen演算法也會選擇使用這兩個壞字元位移的最大值。如此一來可以實現出不比Boyer-Moore-Horspool演算法或Quick Search Algorithm還要慢的演算法。

Boyer-Moore-MagicLen的過程

直接舉個例子來逐步說明Boyer-Moore-MagicLen演算法：

HERE IS A SIMPLE EXAMPLE, WHICH CONTAINS MULTIPLE EXAMPLES. SIXLEE IS A WRONG WORD. EXAMPLEEXAMPLE

現在要搜尋以上這段文字內所有的EXAMPLE字串。

一開始的時候，要搜尋的樣本的第一個字元會對齊於原文中索引0的位置。

HERE IS A SIMPLE EXAMPLE, WHICH CONTAINS MULTIPLE EXAMPLES. SIXLEE IS A WRONG WORD. EXAMPLEEXAMPLE
EXAMPLE

接著從樣本尾端開始往前判斷該位置的字元是否與原文中對應位置的字元相符合。在這裡樣本EXAMPLE的尾端E，所對應的原文字元是S，並不相同，所以樣本無法匹配成功，此時會得到兩個壞字元，一個是正在匹配的原文範圍的最後一個字元E，另一個是其下一個字元 (空格)。

壞字元位移的目的是要把EXAMPLE這個樣本往右移動最少幾個索引值後，樣本本身所含有的壞字元能和剛剛在原文中發現的壞字元對齊。如果樣本右移之後並沒有辦法對齊「壞字元」，位移目的則會改為把EXAMPLE這個樣本往右移動最少幾個索引值後，樣本的第1個字元會在原文的「壞字元」的下一個索引位置。

因此，若壞字元是S，則須使樣本向右位移7個索引值；若壞字元是 (空格)，則須使樣本向右位移8個索引值。在挑選最大壞字元位移值的原則下，我們會選擇將樣本向右位移8個索引值。

HERE IS A SIMPLE EXAMPLE, WHICH CONTAINS MULTIPLE EXAMPLES. SIXLEE IS A WRONG WORD. EXAMPLEEXAMPLE
        EXAMPLE

接著一樣，在這裡樣本EXAMPLE的尾端E，所對應的原文字元是L，並不相同，所以樣本無法匹配成功，此時會得到兩個壞字元，一個是正在匹配的原文範圍的最後一個字元L，另一個是其下一個字元E。

因此，若壞字元是L，則須使樣本向右位移1個索引值；若壞字元是E，則須使樣本向右位移1個索引值。所以樣本向右位移1個索引值。

HERE IS A SIMPLE EXAMPLE, WHICH CONTAINS MULTIPLE EXAMPLES. SIXLEE IS A WRONG WORD. EXAMPLEEXAMPLE
         EXAMPLE

在這裡樣本尾端的MPLE有匹配成功，但是A和其所對應的原文字元是I，並不相同，所以樣本無法匹配成功，此時會得到兩個壞字元，一個是正在匹配的原文範圍的最後一個字元E，另一個是其下一個字元 (空格)。

因此，若壞字元是E，則須使樣本向右位移6個索引值；若壞字元是 (空格)，則須使樣本向右位移8個索引值。在挑選最大壞字元位移值的原則下，我們會選擇將樣本向右位移8個索引值。

HERE IS A SIMPLE EXAMPLE, WHICH CONTAINS MULTIPLE EXAMPLES. SIXLEE IS A WRONG WORD. EXAMPLEEXAMPLE
                 EXAMPLE

重做上面的步驟從樣本尾端開始檢查字元，發現這個位置正好符合我們要找的樣本。那如果要繼續搜尋下去的話該怎麼做呢？在這時候可以把正在匹配的原文範圍的下一個字元當作是壞字元，也就是,。

若壞字元是,，則須使樣本向右位移8個索引值。

HERE IS A SIMPLE EXAMPLE, WHICH CONTAINS MULTIPLE EXAMPLES. SIXLEE IS A WRONG WORD. EXAMPLEEXAMPLE
                         EXAMPLE

接下來的步驟就都和上述的一樣了。完整過程如下：

HERE IS A SIMPLE EXAMPLE, WHICH CONTAINS MULTIPLE EXAMPLES. SIXLEE IS A WRONG WORD. EXAMPLEEXAMPLE
EXAMPLE

如此一來，找到最後，可以知道EXAMPLE字串開始於文字中索引值為17, 50, 84, 91的位置。

若要做反向搜尋，過程如下：

HERE IS A SIMPLE EXAMPLE, WHICH CONTAINS MULTIPLE EXAMPLES. SIXLEE IS A WRONG WORD. EXAMPLEEXAMPLE
EXAMPLE

如此一來，找到最後，可以知道EXAMPLE字串開始於文字中索引值為91, 84, 50, 17的位置。

Boyer-Moore-MagicLen的壞字元位移表

了解Boyer-Moore-MagicLen的運作原理後，接著來談談怎麼樣才能快速進行「壞字元位移」。其實不論是Boyer-Moore-Horspool演算法還是Quick Search Algorithm，壞字元位移的計算方式都是先產生一個集合來儲存樣本的字元從尾端開始往前看的出現順序。

比如說，樣本EXAMPLE的P，它就是從尾端開始算起的第3個字元，而M則是從尾端開始算起的第4個字元。因此若要把P或M移動到目前樣本尾端E的位置，則需要分別將樣本往右位移2或3個索引值。這個計算方式得利於Boyer-Moore-Horspool演算法和Quick Search Algorithm永遠都是選擇目前判斷的原文範圍的最後一個字元或其下一個字元作為壞字元的作法，如果是像Boyer-Moore演算法那樣字是選擇好後綴之前的字元作為壞字元的話，那麼計算壞字元位移的方式就會變得複雜很多，更不用說計算好後綴位移的複雜程度了。

所以樣本EXAMPLE經過上述的方式，所建立出來的「壞字元位移表」如下：

T['E'] = 0;
T['L'] = 1;
T['P'] = 2;
T['M'] = 3;
T['A'] = 4;
T['X'] = 5;
T[others] = 7;

然而這邊似乎出現了一個很奇怪的情形，T['E'] = 0不就表示不移動嗎？

如以下這個例子：

ABCDEFEXAMPLE
EXAMPLE

壞字元為E時，接下來該樣本該如何位移？根本不能動對吧？也就是說這個壞字元位移表是會有問題的，我們並不能把樣本最尾端的字元也算進去，所以正確的「壞字元位移表」應如下：

T['L'] = 1;
T['P'] = 2;
T['M'] = 3;
T['A'] = 4;
T['X'] = 5;
T['E'] = 6;
T[others] = 7;

如此一來就知道要把樣本往右位移6個索引值。

ABCDEFEXAMPLE
      EXAMPLE

但如果壞字元並不是正在匹配的原文範圍的最後一個字元，而是其下一個字元呢？難道把原先的「壞字元位移表」都加一就好了嗎？像是這樣：

T['L'] = 2;
T['P'] = 3;
T['M'] = 4;
T['A'] = 5;
T['X'] = 6;
T['E'] = 7;
T[others] = 8;

看似可行，但如果是以下遇到例子，要怎麼讓樣本位移呢？

AEXAMPLEABCDEFG
EXAMPLE

壞字元為E時，如果直接查詢「壞字元位移表」，會得到位移7的結果。

AEXAMPLEABCDEFG
       EXAMPLE

這樣的位移肯定是有問題的，因為原文中索引1開始就有出現EXAMPLE子字串，而它卻被跳過了！

為了解決這個問題，我們可以有兩種解決方法，第一種是直接修改選擇使用正在匹配的原文範圍的下一個字元作為壞字元時的「壞字元位移表」，除了把原本的「壞字元位移表」的位移值都加1之外，還要把樣本最尾端的字元位移量改為1，只不過這樣在運算時就會需要兩個「壞字元位移表」。如果要沿用「壞字元位移表」的話，可以在計算時，先去判斷正在匹配的原文範圍的下一個字元是否就是樣本尾端字元，如果是的話就直接使用位移值1，如果不是的話就再進行查表並將結果加1。後者會是筆者比較建議的方式。

Boyer-Moore-MagicLen演算法的程式實作

/// Boyer-Moore-MagicLen演算法(正向)。
pub fn boyer_moore_magiclen(text: &[char], pattern: &[char]) -> Vec<usize> {
    let text_len = text.len();
    let pattern_len = pattern.len();

    if text_len == 0 || pattern_len == 0 || text_len < pattern_len {
        return vec![];
    }

    let pattern_len_dec = pattern_len - 1;
    let pattern_len_inc = pattern_len + 1;

    let mut bad_char_shift_map: HashMap<char, usize> = HashMap::with_capacity(pattern_len_dec);

    for (i, c) in pattern.iter().copied().take(pattern_len_dec).enumerate() {
        bad_char_shift_map.insert(c, pattern_len_dec - i);
    }

    let last_pattern_char = pattern[pattern_len_dec];

    let mut shift = 0;

    let end_index = text_len - pattern_len;

    let mut result = vec![];

    'outer: loop {
        for (i, pc) in pattern.iter().copied().enumerate().rev() {
            if text[shift + i] != pc {
                let p = shift + pattern_len;
                if p == text_len {
                    break 'outer;
                }
                shift += bad_char_shift_map.get(&text[shift + pattern_len_dec]).copied().unwrap_or(pattern_len).max(
                    {
                        let c = text[p];

                        if c == last_pattern_char {
                            1
                        } else {
                            bad_char_shift_map.get(&c).map(|&c| c + 1).unwrap_or(pattern_len_inc)
                        }
                    }
                );
                if shift > end_index {
                    break 'outer;
                }
                continue 'outer;
            }
        }
        result.push(shift);

        if shift == end_index {
            break;
        }

        shift += bad_char_shift_map.get(&text[shift + pattern_len_dec]).copied().unwrap_or(pattern_len).max(
            {
                let c = text[shift + pattern_len];

                if c == last_pattern_char {
                    1
                } else {
                    bad_char_shift_map.get(&c).map(|&c| c + 1).unwrap_or(pattern_len_inc)
                }
            }
        );
        if shift > end_index {
            break;
        }
    }

    result
}

/// Boyer-Moore-MagicLen演算法(反向)。
pub fn boyer_moore_magiclen_rev(text: &[char], pattern: &[char]) -> Vec<usize> {
    let text_len = text.len();
    let pattern_len = pattern.len();

    if text_len == 0 || pattern_len == 0 || text_len < pattern_len {
        return vec![];
    }

    let pattern_len_dec = pattern_len - 1;
    let pattern_len_inc = pattern_len + 1;

    let mut bad_char_shift_map: HashMap<char, usize> = HashMap::with_capacity(pattern_len_dec);

    for (i, c) in pattern.iter().copied().enumerate().rev().take(pattern_len_dec) {
        bad_char_shift_map.insert(c, i);
    }

    let first_pattern_char = pattern[0];

    let mut shift = text_len - 1;

    let start_index = pattern_len_dec;

    let mut result = vec![];

    'outer: loop {
        for (i, pc) in pattern.iter().copied().enumerate() {
            if text[shift - pattern_len_dec + i] != pc {
                if shift < pattern_len {
                    break 'outer;
                }
                shift -= bad_char_shift_map.get(&text[shift - pattern_len_dec]).copied().unwrap_or(pattern_len).max(
                    {
                        let c = text[shift - pattern_len];

                        if c == first_pattern_char {
                            1
                        } else {
                            bad_char_shift_map.get(&c).map(|&c| c + 1).unwrap_or(pattern_len_inc)
                        }
                    }
                );
                if shift < start_index {
                    break 'outer;
                }
                continue 'outer;
            }
        }
        result.push(shift - pattern_len_dec);

        if shift == start_index {
            break;
        }

        let s = bad_char_shift_map.get(&text[shift - pattern_len_dec]).copied().unwrap_or(pattern_len).max(
            {
                let c = text[shift - pattern_len];

                if c == first_pattern_char {
                    1
                } else {
                    bad_char_shift_map.get(&c).map(|&c| c + 1).unwrap_or(pattern_len_inc)
                }
            }
        );
        if shift < s {
            break;
        }
        shift -= s;
        if shift < start_index {
            break;
        }
    }

    result
}

/**
 * Boyer-Moore-MagicLen演算法(正向)。
 */
public static Integer[] boyerMooreMagicLen(final char[] text, final char[] pattern) {
    int textLength = text.length;
    int patternLength = pattern.length;

    if (textLength == 0 || patternLength == 0 || textLength < patternLength) {
        return new Integer[0];
    }

    final int patternLengthDec = patternLength - 1;

    final HashMap<Character, Integer> badCharShiftMap = new HashMap<>(patternLengthDec);

    for (int i = 0; i < patternLengthDec; ++i) {
        badCharShiftMap.put(pattern[i], patternLengthDec - i);
    }

    final char lastPatternChar = pattern[patternLengthDec];

    int shift = 0;

    final int endIndex = textLength - patternLength;

    final ArrayList<Integer> result = new ArrayList<>();

    outer:
    while (true) {
        for (int i = patternLengthDec; i >= 0; --i) {
            if (text[shift + i] != pattern[i]) {
                final int p = shift + patternLength;
                if (p == textLength) {
                    break outer;
                }
                final int s1 = badCharShiftMap.getOrDefault(text[shift + patternLengthDec], patternLength);
                final char c = text[p];
                final int s2 = c == lastPatternChar ? 1 : (badCharShiftMap.getOrDefault(c, patternLength) + 1);
                shift += Math.max(s1, s2);
                if (shift > endIndex) {
                    break outer;
                }
                continue outer;
            }
        }
        result.add(shift);

        if (shift == endIndex) {
            break;
        }

        final int s1 = badCharShiftMap.getOrDefault(text[shift + patternLengthDec], patternLength);
        final char c = text[shift + patternLength];
        final int s2 = c == lastPatternChar ? 1 : (badCharShiftMap.getOrDefault(c, patternLength) + 1);
        shift += Math.max(s1, s2);
        if (shift > endIndex) {
            break;
        }
    }

    return result.toArray(new Integer[result.size()]);
}

/**
 * Boyer-Moore-MagicLen演算法(反向)。
 */
public static Integer[] boyerMooreMagicLenRev(final char[] text, final char[] pattern) {
    int textLength = text.length;
    int patternLength = pattern.length;

    if (textLength == 0 || patternLength == 0 || textLength < patternLength) {
        return new Integer[0];
    }

    final int patternLengthDec = patternLength - 1;

    final HashMap<Character, Integer> badCharShiftMap = new HashMap<>(patternLengthDec);

    for (int i = patternLengthDec; i >= 1; --i) {
        badCharShiftMap.put(pattern[i], i);
    }

    final char firstPatternChar = pattern[0];

    int shift = textLength - 1;

    final int startIndex = patternLengthDec;

    final ArrayList<Integer> result = new ArrayList<>();

    outer:
    while (true) {
        for (int i = 0; i < patternLength; ++i) {
            if (text[shift - patternLengthDec + i] != pattern[i]) {
                final int p = shift - patternLength;
                if (p < 0) {
                    break outer;
                }
                final int s1 = badCharShiftMap.getOrDefault(text[shift - patternLengthDec], patternLength);
                final char c = text[p];
                final int s2 = c == firstPatternChar ? 1 : (badCharShiftMap.getOrDefault(c, patternLength) + 1);
                shift -= Math.max(s1, s2);
                if (shift < startIndex) {
                    break outer;
                }
                continue outer;
            }
        }
        result.add(shift - patternLengthDec);

        if (shift == startIndex) {
            break;
        }

        final int s1 = badCharShiftMap.getOrDefault(text[shift - patternLengthDec], patternLength);
        final char c = text[shift - patternLength];
        final int s2 = c == firstPatternChar ? 1 : (badCharShiftMap.getOrDefault(c, patternLength) + 1);
        shift -= Math.max(s1, s2);
        if (shift < startIndex) {
            break;
        }
    }

    return result.toArray(new Integer[result.size()]);
}

/**
 * Boyer-Moore-MagicLen演算法(正向)。
 */
function boyerMooreMagicLen(text: string, pattern: string) {
    const textLength = text.length;
    const patternLength = pattern.length;
 
    if (textLength === 0 || patternLength === 0 || textLength < patternLength) {
        return [];
    }
 
    const patternLengthDec = patternLength - 1;
 
    const badCharShiftMap: Record<string, number> = {};
 
    for (let i = 0;i < patternLengthDec;++i) {
        badCharShiftMap[pattern[i]] = patternLengthDec - i;
    }
 
    const lastPatternChar = pattern[patternLengthDec];
 
    let shift = 0;
 
    const endIndex = textLength - patternLength;
 
    const result = [];
 
    outer:
    for (; ;) {
        for (let i = patternLengthDec;i >= 0;i--) {
            if (text[shift + i] !== pattern[i]) {
                const p = shift + patternLength;
                if (p === textLength) {
                    break outer;
                }
                let s1 = badCharShiftMap[text[shift + patternLengthDec]];
                if (typeof s1 === "undefined") {
                    s1 = patternLength;
                }
                const c = text[p];
                let s2;
                if (c === lastPatternChar) {
                    s2 = 1;
                } else {
                    s2 = badCharShiftMap[c];
                    if (typeof s2 === "undefined") {
                        s2 = patternLength + 1;
                    } else {
                        s2 += 1;
                    }
                }
                shift += Math.max(s1, s2);
                if (shift > endIndex) {
                    break outer;
                }
                continue outer;
            }
        }
        result.push(shift);
 
        if (shift === endIndex) {
            break;
        }
 
        let s1 = badCharShiftMap[text[shift + patternLengthDec]];
        if (typeof s1 === "undefined") {
            s1 = patternLength;
        }
        const c = text[shift + patternLength];
        let s2;
        if (c === lastPatternChar) {
            s2 = 1;
        } else {
            s2 = badCharShiftMap[c];
            if (typeof s2 === "undefined") {
                s2 = patternLength + 1;
            } else {
                s2 + 1;
            }
        }
        shift += Math.max(s1, s2);
        if (shift > endIndex) {
            break;
        }
    }
 
    return result;
}
 
/**
 * Boyer-Moore-MagicLen演算法(反向)。
 */
function boyerMooreMagicLenRev(text: string, pattern: string) {
    const textLength = text.length;
    const patternLength = pattern.length;
 
    if (textLength === 0 || patternLength === 0 || textLength < patternLength) {
        return [];
    }
 
    const patternLengthDec = patternLength - 1;
 
    const badCharShiftMap: Record<string, number> = {};
 
    for (let i = patternLengthDec;i >= 1;i--) {
        badCharShiftMap[pattern[i]] = i;
    }
 
    const firstPatternChar = pattern[0];
 
    let shift = textLength - 1;
 
    const startIndex = patternLengthDec;
 
    const result = [];
 
    outer:
    for (; ;) {
        for (let i = 0;i < patternLength;++i) {
            if (text[shift - patternLengthDec + i] !== pattern[i]) {
                const p = shift - patternLength;
                if (p < 0) {
                    break outer;
                }
                let s1 = badCharShiftMap[text[shift - patternLengthDec]];
                if (typeof s1 === "undefined") {
                    s1 = patternLength;
                }
                const c = text[p];
                let s2;
                if (c === firstPatternChar) {
                    s2 = 1;
                } else {
                    s2 = badCharShiftMap[c];
                    if (typeof s2 === "undefined") {
                        s2 = patternLength + 1;
                    } else {
                        s2 += 1;
                    }
                }
                shift -= Math.max(s1, s2);
                if (shift < startIndex) {
                    break outer;
                }
                continue outer;
            }
        }
        result.push(shift - patternLengthDec);
 
        if (shift === startIndex) {
            break;
        }
 
        let s1 = badCharShiftMap[text[shift - patternLengthDec]];
        if (typeof s1 === "undefined") {
            s1 = patternLength;
        }
        const c = text[shift - patternLength];
        let s2;
        if (c === firstPatternChar) {
            s2 = 1;
        } else {
            s2 = badCharShiftMap[c];
            if (typeof s2 === "undefined") {
                s2 = patternLength + 1;
            } else {
                s2 += 1;
            }
        }
        shift -= Math.max(s1, s2);
        if (shift < startIndex) {
            break;
        }
    }
 
    return result;
}

// Boyer-Moore-MagicLen演算法(正向)。
func BoyerMooreMagicLen(text []rune, pattern []rune) []int {
	textLength := len(text)
	patternLength := len(pattern)

	if textLength == 0 || patternLength == 0 || textLength < patternLength {
		return make([]int, 0)
	}

	patternLengthDec := patternLength - 1

	badCharShiftMap := make(map[rune]int)

	for i := 0; i < patternLengthDec; i += 1 {
		badCharShiftMap[pattern[i]] = patternLengthDec - i
	}

	lastPatternChar := pattern[patternLengthDec]

	shift := 0

	endIndex := textLength - patternLength

	var result = make([]int, 0)

outer:
	for {
		for i := patternLengthDec; i >= 0; i -= 1 {
			if text[shift+i] != pattern[i] {
				p := shift + patternLength
				if p == textLength {
					break outer
				}
				s1, ok := badCharShiftMap[text[shift+patternLengthDec]]
				if !ok {
					s1 = patternLength
				}
				c := text[p]
				var s2 int
				if c == lastPatternChar {
					s2 = 1
				} else {
					s2, ok = badCharShiftMap[c]
					if ok {
						s2 += 1
					} else {
						s2 = patternLength + 1
					}
				}
				if s1 > s2 {
					shift += s1
				} else {
					shift += s2
				}
				if shift > endIndex {
					break outer
				}
				continue outer
			}
		}
		result = append(result, shift)

		if shift == endIndex {
			break
		}

		s1, ok := badCharShiftMap[text[shift+patternLengthDec]]
		if !ok {
			s1 = patternLength
		}
		c := text[shift+patternLength]
		var s2 int
		if c == lastPatternChar {
			s2 = 1
		} else {
			s2, ok = badCharShiftMap[c]
			if ok {
				s2 += 1
			} else {
				s2 = patternLength + 1
			}
		}
		if s1 > s2 {
			shift += s1
		} else {
			shift += s2
		}
		if shift > endIndex {
			break
		}
	}

	return result
}

// Boyer-Moore-MagicLen演算法(反向)。
func BoyerMooreMagicLenRev(text []rune, pattern []rune) []int {
	textLength := len(text)
	patternLength := len(pattern)

	if textLength == 0 || patternLength == 0 || textLength < patternLength {
		return make([]int, 0)
	}

	patternLengthDec := patternLength - 1

	badCharShiftMap := make(map[rune]int)

	for i := patternLengthDec; i >= 1; i -= 1 {
		badCharShiftMap[pattern[i]] = i
	}

	firstPatternChar := pattern[0]

	shift := textLength - 1

	startIndex := patternLengthDec

	var result = make([]int, 0)

outer:
	for {
		for i := 0; i < patternLength; i += 1 {
			if text[shift-patternLengthDec+i] != pattern[i] {
				p := shift - patternLength
				if p < 0 {
					break outer
				}
				s1, ok := badCharShiftMap[text[shift-patternLengthDec]]
				if !ok {
					s1 = patternLength
				}
				c := text[p]
				var s2 int
				if c == firstPatternChar {
					s2 = 1
				} else {
					s2, ok = badCharShiftMap[c]
					if ok {
						s2 += 1
					} else {
						s2 = patternLength + 1
					}
				}
				if s1 > s2 {
					shift -= s1
				} else {
					shift -= s2
				}
				if shift < startIndex {
					break outer
				}
				continue outer
			}
		}
		result = append(result, shift-patternLengthDec)

		if shift == startIndex {
			break
		}

		s1, ok := badCharShiftMap[text[shift-patternLengthDec]]
		if !ok {
			s1 = patternLength
		}
		c := text[shift-patternLength]
		var s2 int
		if c == firstPatternChar {
			s2 = 1
		} else {
			s2, ok = badCharShiftMap[c]
			if ok {
				s2 += 1
			} else {
				s2 = patternLength + 1
			}
		}
		if s1 > s2 {
			shift -= s1
		} else {
			shift -= s2
		}
		if shift < startIndex {
			break
		}
	}

	return result
}

如果要搜尋的資料可能的值的數量範圍並不大，例如只有ISO-8859-1編碼的字元值範圍，則可以直接使用長度為256的整數陣列來製作「壞字元位移表」，效能會比使用HashMap還要好。不僅如此，事實上，所有支援自我同步(self-synchronizing)的字串編碼(如UTF-8)都能使用長度為256的整數陣列的「壞字元位移表」來正確運行Boyer-Moore相關的演算法。

Boyer-Moore-MagicLen演算法的複雜度

這邊計算的複雜度是以成功搜尋到一個樣本位置之後就結束演算法為基準。

以#{{n}}#來表示要搜尋的資料筆數。以#{{m}}#來表示要搜尋的樣本資料筆數。以#{{k}}#來表示要搜尋的資料可能的值的數量。

項目	複雜度	備註
最差時間複雜度	#{{O(m + k) + O(nm)}}#	壞字元位移量都是`1`。
最佳時間複雜度	#{{O(m + k) + O({n \over m})}}#	壞字元位移量都是`m`或`m + 1`。
平均時間複雜度	#{{O(m + k) + \Omega({n \over m})}}#	平均時間複雜度不容易估計。
最差空間複雜度	#{{O(m + k)}}#