C++用BF算法实现模式串匹配 使用定长顺序存储，返回模式串在目标串中的位置的代码

在C++中，Boyer-Moore (BF) 算法是一种用于字符串搜索的有效方法，它利用了模式串的一些特性，避免了不必要的字符比较。以下是一个简单的Boyer-Moore算法的实现，使用定长顺序存储（即预处理模式串后缀函数），寻找模式串在目标串中的起始位置：

#include <iostream>
#include <vector>

// 计算模式串s的后缀函数，存储在suffix数组中
void computeSuffixFunction(const std::string& s, std::vector<int>& suffixArray) {
    int n = s.length();
    for (int i = 1; i < n; ++i) {
        while (i > 0 && s[i] != s[i - suffixArray[i]])
            suffixArray[i] = suffixArray[i - 1];
        if (s[i] == s[i - suffixArray[i]])
            suffixArray[i] = suffixArray[i - 1] + 1;
    }
}

// 从右向左移动主串的位置，使用BF算法寻找匹配
int BoyerMooreSearch(const std::string& text, const std::string& pattern, std::vector<int>& suffixArray) {
    int m = pattern.length(), n = text.length();
    int i = m - 1, j = n;

    // 如果模式串比主串还短，直接返回
    if (n < m)
        return -1;

    while (i >= 0) {
        if (text[j] == pattern[i]) { // 字符相等，检查是否完全匹配
            if (j - i < m)
                return j - m + 1; // 如果是，返回匹配位置
            else { // 检查后缀函数，移动主串
                i - i]; // 同步主串
            }
        } else { // 字符不等，跳过最长不匹配前缀
            i = max(0, i - suffixArray[m - 1]);
        }
    }

    return -1; // 没有找到匹配
}

int main() {
    std::string pattern = "abab";
    std::string text = "babaabab";

    // 计算模式串的后缀函数
    std::vector<int> suffixArray(pattern.size());
    computeSuffixFunction(pattern, suffixArray);

    // 在文本中查找模式串
    int position = BoyerMooreSearch(text, pattern, suffixArray);
    if (position != -1)
        std::cout << "Pattern found at index: " << position << std::endl;
    else
        std::cout << "Pattern not found" << std::endl;

    return 0;
}

在这个例子中，我们首先计算了模式串的后缀函数，然后使用Boyer-Moore算法在目标串中查找。如果找到匹配，返回匹配位置；如果没有找到，则返回-1。