一、 用BF算法实现模式串匹配。 要求：使用定长顺序存储，返回模式串在目标串中的位置。 目标串：abcabebfschaglwke 模式串：bfscha 用C++写

在使用BF（Boyer-Moore字符串搜索算法）实现模式串匹配时，它是一种快速的搜索算法，通过预处理模式串信息避免不必要的字符比较。下面是一个简单的C++实现，假设模式串已经在内存中预先处理过：

#include <iostream>
#include <vector>

// 定义BF算法的辅助函数，获取模式串结束的位置和坏字符距离
void getBadCharShift(const std::string &pattern, int badChars[], int len) {
    for (int i = 0; i < len; ++i) {
        badChars[pattern[i]] = len - (i + 1);
    }
}

// 主要的BF匹配函数
int BoyerMooreSearch(const std::string &text, const std::string &pattern) {
    int m = pattern.length();
    int n = text.length();

    // 计算坏字符表和好后缀表
    int badChars[m];
    getBadCharShift(pattern, badChars, m);

    int i = m - 1;
    while (i < n) {
        if (text[i] == pattern[i]) {  // 如果当前字符匹配
            if (i == 0) {  // 模式串完全匹配
                return i;
            } else {
                i--;
                continue;
            }
        }

        // 判断是否可以用坏字符规则跳过
        int skip = std::min(badChars[text[i]], m - i - 1);
        i += skip;

        // 如果模式串未结束，检查好后缀表
        while (i < n && pattern[m - 1] != text[i]) {
            i++;
        }
    }
    return -1;  // 没有找到匹配
}

int main() {
    std::string target = "abcabebfschaglwke";
    std::string pattern = "bfscha";

    int position = BoyerMooreSearch(target, pattern);
    if (position != -1) {
        std::cout << "Pattern found at position: " << position << std::endl;
    } else {
        std::cout << "Pattern not found" << std::endl;
    }

    return 0;
}

这个程序首先计算了模式串的坏字符表和好后缀表，然后在目标串中从右向左进行查找。如果遇到不匹配，会利用预处理的信息尽可能地跳过字符。