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

要使用宽度优先搜索（BFS）算法在一个字符串 `s` 中查找子串 `t` 的最后一次出现位置，我们可以按照以下步骤操作：

1. **创建队列**：初始化一个队列，放入子串 `t` 的起始索引（0），表示我们从第一个字符开始查找。

2. **广度优先遍历**：对于每个子串 `t` 的起始位置 `i`，检查 `s[i:i+len(t)-1]` 是否等于 `t`。如果是，找到子串的位置，然后从这个位置往后的每一个位置，如果也是 `t` 的前缀，则加入队列，以便后续检查。

3. **更新最大位置**：每当找到一个新的匹配位置，更新全局变量（如 `lastAppearance` 或者类似的数据结构）来保存到目前为止找到的最远的子串 `t` 的位置。

4. **重复直到队列为空**：只要队列不为空，就继续执行第二步。

5. **返回结果**：遍历完成后，`lastAppearance` 就是子串 `t` 在 `s` 中的最后一次出现位置。

下面是C++代码实现：

#include <iostream>
#include <queue>
#include <string>

int lastAppearance(const std::string& s, const std::string& t) {
    int n = s.length(), m = t.length();
    if (m > n)
        return -1; // 子串 t 长度过长，不可能出现在 s 中

    bool seen[m]; // 前缀标志数组，标记是否遇到过子串 t 的某个前缀
    for (int i = 0; i < m; ++i)
        seen[i] = false;

    // 初始化队列，放 t 的起始位置
    std::queue<int> queue;
    queue.push(0);

    while (!queue.empty()) {
        int i = queue.front(); queue.pop();
        if (i + m <= n && s.substr(i, m) == t) {
            // 找到了子串 t，更新 lastAppearance
            lastAppearance = i;
            seen[m - 1] = true; // 标记已遇到子串的尾部
        }

        // 如果当前位置后面还有 t 的可能前缀
        if (seen[t[i]]) continue; // 已经遇到过该前缀，跳过

        // 检查下一个位置
        if (i + 1 < n)
            queue.push(i + 1);
    }

    return lastAppearance;
}

int main() {
    std::string s = "abcdabcd";
    std::string t = "abc";
    int result = lastAppearance(s, t);
    std::cout << "Last occurrence of " << t << " in " << s << " is at position " << result << std::endl;

    s = "aaaaa";
    t = "aaa";
    result = lastAppearance(s, t);
    std::cout << "Last occurrence of " << t << " in " << s << " is at position " << result << std::endl;

    return 0;
}