假设字符串s采用顺序串储存，设计一个基于BF的算法，在串s中查找子串t最后一次出现的位置。例如，当s=“abcdabcd”，t=“abc”时结果为4，当s=“aaaaa“，t=”aaa“时结果为2

要使用Boyer-Moore (BM) 字符串搜索算法来查找子串 `t` 在字符串 `s` 中最后一次出现的位置，这个算法利用了两个启发式规则，即坏字符规则（Bad Character Rule）和好后缀规则（Good Suffix Rule），以提高搜索效率。这里我们主要关注坏字符规则，因为它不需要额外的数据结构。

首先，你需要计算 `t` 的坏字符数组 `badChar[]`，其中 `badChar[i]` 是从 `t[0]` 到 `t[i-1]` 这个前缀中的最右边与 `s` 中字符不匹配的字符位置。如果没有这样的字符，则设置为 `strlen(t)`。

然后，对于 `s` 的每个可能的结束点 `i`（从 `s.length() - t.length()` 开始），执行以下步骤：

1. **坏字符跳过**：如果 `s[i]` 和 `t[strlen(t)-1]` 不匹配，根据 `badChar[strlen(t)-1]` 跳过最多 `min(len(s)-i, badChar[strlen(t)-1])` 个字符。这是因为我们可以直接忽略与 `t` 前缀字符不匹配的后续字符。

2. **回溯检查**：如果 `s[i]` 等于 `t[strlen(t)-1]`，则从 `i+1` 开始检查下一个字符是否匹配，直到找到不匹配或到达 `s` 的末尾。这是基本的字符串比较过程。

在这个过程中，找到 `t` 最后一次出现的位置时，`i` 就是你所寻找的答案。

下面是算法的基本伪代码：

int BM_search(const string& s, const string& t) {
    int n = s.size(), m = t.size();
    vector<int> badChar(m);
    // 初始化坏字符数组
    for (int i = 0; i < m; ++i) {
        while (i + badChar[i] < m && s[n - m + i + 1] == t[i + badChar[i]]) {
            ++badChar[i];
        }
    }

    int pos = n;
    // 从后往前搜索
    for (int i = n - m; i >= 0; --i) {
        if (s.substr(i, m) == t) {
            pos = i;
            break;
        } else if (i + m <= n && s[i + m - 1] != t[m - 1] && badChar[m - 1] > 0) {
            i += min(m - 1, badChar[m - 1]);
        }
    }

    return pos;
}