C++ 实现 BM 字符串匹配算法

BM（Boyer-Moore）算法是一种经典的字符串匹配算法，其主要思路是从模式串的尾部开始匹配，根据坏字符规则和好后缀规则来快速定位匹配位置，从而实现快速的字符串匹配。

下面是 C++ 实现 BM 搜索的代码：

#include <iostream>
#include <cstring>
using namespace std;

const int MAX = 256; //字符集大小

void BM_Search(const char* str, const char* pattern)
{
    int len_str = strlen(str);
    int len_pat = strlen(pattern);

    int badChars[MAX]; //坏字符表
    for (int i = 0; i < MAX; i++)
        badChars[i] = -1;

    //构建坏字符表
    for (int i = 0; i < len_pat; i++)
        badChars[pattern[i]] = i;

    int suffix[len_pat]; //后缀表
    bool prefix[len_pat]; //前缀表

    //初始化
    for (int i = 0; i < len_pat; i++) {
        suffix[i] = -1;
        prefix[i] = false;
    }

    //构建后缀表和前缀表
    for (int i = 0; i < len_pat - 1; i++) {
        int j = i;
        int k = 0;
        while (j >= 0 && pattern[j] == pattern[len_pat - 1 - k]) {
            j--;
            k++;
            suffix[k] = j + 1;
        }
        if (j == -1) prefix[k] = true;
    }

    //匹配
    int i = 0;
    while (i <= len_str - len_pat) {
        int j = len_pat - 1;
        while (j >= 0 && pattern[j] == str[i + j])
            j--;
        if (j < 0) { //匹配成功
            cout << '匹配位置：' << i << endl;
            i += (i + len_pat < len_str) ? len_pat - badChars[str[i + len_pat]] : 1;
        }
        else {
            int x = j - suffix[j];
            int y = 0;
            if (j < len_pat - 1) {
                y = prefix[len_pat - 1 - j];
                x = (x > y) ? x : y;
            }
            i += x - badChars[str[i + x]];
        }
    }
}

int main()
{
    char str[] = 'ABCAABCABCAABCAABCAABCD';
    char pattern[] = 'ABCAABCD';
    BM_Search(str, pattern);
    return 0;
}

在上述代码中，我们首先构建了坏字符表和后缀表、前缀表，然后在匹配时按照坏字符规则和好后缀规则进行匹配，从而实现快速的字符串匹配。

在使用该算法时，需要注意处理边界情况，比如模式串为空或者长度大于字符串长度等情况。