C++写模式匹配bf算法

BF（Boyer-Moore Hunt）算法是一种用于文本搜索的快速字符串匹配算法，它的名字来自于两位发明者John H. Boyer和J Strother Moore。C++编写BF算法的基本步骤包括：

1. **预处理阶段**：构建坏字符表和好后缀表。坏字符表记录每个字符最后一次出现的位置，好后缀表则存储从右向左查找时的偏移量，使得字符串可以跳过已经确定不可能的匹配部分。

struct BadCharShift {
    char ch;
    int shift;
};

void buildBadCharTable(const string& pattern, vector<BadCharShift>& badChars) {
    for (int i = 0; i < pattern.length(); ++i) {
        badChars[pattern[i] - 'a'].shift = i + 1;
    }
}

vector<int> buildGoodSuffixTable(const string& pattern) {
    // ... 实现计算好后缀表的过程
}

2. **搜索阶段**：在主字符串中遍历，首先移动到下一个未匹配位置。对于当前字符，利用坏字符表找到最大后退距离，然后利用好后缀表更新当前位置。

int bfSearch(string text, const string& pattern) {
    int patternLen = pattern.length();
    vector<BadCharShift> badChars;
    buildBadCharTable(pattern, badChars);
    
    int textIndex = 0;
    while (textIndex <= text.length() - patternLen) {
        int j = patternLen - 1;
        while (j >= 0 && text[textIndex + j] == pattern[j]) {
            --j;
        }
        
        if (j == -1) {
            // 找到了匹配
            return textIndex;
        }
        
        int badCharShift = badChars[text[textIndex + j] - 'a'].shift;
        textIndex += max(badCharShift, patternLen - j - 1);
    }
    
    return -1; // 没有找到匹配
}