如何實作文本編輯器中的查找替換功能？——BF算法

1 BM（Boyer-Moore）算法

它是一種非常高效的字元串比對算法，有實驗統計，它的性能是著名的KMP算法的 3 到 4 倍。BM 算法核心思想是，利用模式串本身的特點，在模式串中某個字元與主串不能比對的時候，将模式串往後多滑動幾位，以此來減少不必要的字元比較，提高比對的效率。BM 算法建構的規則有兩類，壞字元規則和好字尾規則。好字尾規則可以獨立于壞字元規則使用。因為壞字元規則的實作比較耗記憶體，為了節省記憶體，我們可以隻用好字尾規則來實作 BM 算法。

1.1 壞字元規則

BM 算法的比對順序比較特别，它是按照模式串下标從大到小的順序，倒着比對的。我畫了一張圖，你可以看下。我們從模式串的末尾往前倒着比對，當我們發現某個字元沒法比對的時候。我們把這個沒有比對的字元叫作壞字元（主串中的字元）。

1.2 好字尾規則

好字尾規則實際上跟壞字元規則的思路很類似。你看我下面這幅圖。當模式串滑動到圖中的位置的時候，模式串和主串有 2 個字元是比對的，倒數第 3 個字元發生了不比對的情況。

好字尾的處理規則中最核心的内容：

在模式串中，查找跟好字尾比對的另一個子串；
在好字尾的字尾子串中，查找最長的、能跟模式串字首子串比對的字尾子串；

2 各部分代碼如下

#include <iostream>
#include <math.h>
#include <cstring>
using namespace std;

#define MAXNUM 256

// 計算壞字元對應的hashtable
void generateHashTable(char b[], int m, int hashtable[]){
    for(int i = 0; i < m; i++){
        int ascii = (int)b[i];
        // 這樣寫是可以的，會将壞字元放在最右邊兒的位置
        hashtable[ascii] = i;
    }
}

int moveByGS(int j, int m, int suffix[], bool prefix[]){
    // 好字尾長度
    int k = m - 1 - j;
    if(suffix[k] != -1)
        return j - suffix[k] + 1;
    for(int r = j + 2; r <= m - 1; r++){
        if(prefix[m - r])
            return r;
    }
    return m;
}

// 計算好字尾對應的數組
void generateGS(char b[], int m, int suffix[], bool prefix[]){
    // b[0, i]
    for(int i = 0; i < m - 1 ; i++){
        int j = i;
        // 公共字尾串長度
        int k = 0;
        // 妙啊
        while(j >= 0 && b[j] == b[m - 1 - k]){
            j--;
            k++;
            suffix[k] = j + 1;
        }
        if(j == -1)
            prefix[k] = true;
    }
}

// BF算法
int boyerMoore(char a[], int n, char b[], int m){
    // 根據模式串生成hashtable
    int hashtable[MAXNUM + 1];
    // 初始化
    memset(hashtable, -1, sizeof(hashtable));
    generateHashTable(b, m, hashtable);

    // 根據模式串生成suffix、prefix
    int suffix[MAXNUM + 1];
    bool prefix[MAXNUM + 1];
    memset(suffix, -1, sizeof(suffix));
    memset(prefix, false, sizeof(prefix));
    generateGS(b, m, suffix, prefix);
    int i = 0;
    while(i <= n - m){
        int j;
        // BF算法從後往前比對
        for(j = m - 1; j >= 0; j--){
            // 找到壞字元
            if(a[i + j] != b[j])
                break;
        }
        if(j < 0)
            return i;
        // 找到壞字元在模式串中的位置
        int x = j - hashtable[(int)a[i+j]];
        /***********好字尾方法************/
        int y = 0;
        // 如果有好字尾
        if(j < m - 1)
            y = moveByGS(j, m, suffix, prefix);
        i = i + max(x, y);
    }
    return -1;
}