其他板子

主要是这个结构体 $

struct KMP {
    std::vector<int> fail; // 失配数组
    std::string pattern; // 模式串
    KMP() {} // 默认构造函数
    // 构造函数，初始化模式串和失配数组
    KMP(const std::string& p) {
        init(p);
    }
    // 初始化函数，用于初始化模式串和失配数组
    void init(const std::string& p) {
        pattern = p; // 初始化模式串
        fail.resize(pattern.size() + 1); // 初始化失配数组
        fail[0] = -1; // 失配数组第一个元素为-1
        int j = -1; // j表示失配数组的值
        for (int i = 0; i < pattern.size(); i++) { // 遍历模式串
            while (j >= 0 && pattern[i] != pattern[j]) { // 如果失配，则回溯
                j = fail[j]; // 回溯到失配位置的失配数组值
            }
            j++; // 失配数组值加1
            fail[i + 1] = j; // 更新失配数组
        }
    }
    // 匹配函数，返回所有匹配位置
    std::vector<int> match(const std::string& s) {
        std::vector<int> res; // 存储匹配位置
        int j = 0; // j表示失配数组的值
        for (int i = 0; i < s.size(); i++) { // 遍历文本串
            while (j >= 0 && s[i] != pattern[j]) { // 如果失配，则回溯
                j = fail[j]; // 回溯到失配位置的失配数组值
            }
            j++; // 失配数组值加1
            if (j == pattern.size()) { // 如果匹配成功
                res.push_back(i - j + 1); // 存储匹配位置
                j = fail[j]; // 回溯到失配位置的失配数组值
            }
        }
        return res; // 返回所有匹配位置
    }
};

#include<bits/stdc++.h>
struct KMP {
    std::vector<int> fail; // 失配数组
    std::string pattern; // 模式串
    KMP() {} // 默认构造函数
    // 构造函数，初始化模式串和失配数组
    KMP(const std::string& p) {
        init(p);
    }
    // 初始化函数，用于初始化模式串和失配数组
    void init(const std::string& p) {
        pattern = p; // 初始化模式串
        fail.resize(pattern.size() + 1); // 初始化失配数组
        fail[0] = -1; // 失配数组第一个元素为-1
        int j = -1; // j表示失配数组的值
        for (int i = 0; i < pattern.size(); i++) { // 遍历模式串
            while (j >= 0 && pattern[i] != pattern[j]) { // 如果失配，则回溯
                j = fail[j]; // 回溯到失配位置的失配数组值
            }
            j++; // 失配数组值加1
            fail[i + 1] = j; // 更新失配数组
        }
    }
    // 匹配函数，返回所有匹配位置
    std::vector<int> match(const std::string& s) {
        std::vector<int> res; // 存储匹配位置
        int j = 0; // j表示失配数组的值
        for (int i = 0; i < s.size(); i++) { // 遍历文本串
            while (j >= 0 && s[i] != pattern[j]) { // 如果失配，则回溯
                j = fail[j]; // 回溯到失配位置的失配数组值
            }
            j++; // 失配数组值加1
            if (j == pattern.size()) { // 如果匹配成功
                res.push_back(i - j + 1); // 存储匹配位置
                j = fail[j]; // 回溯到失配位置的失配数组值
            }
        }
        return res; // 返回所有匹配位置
    }
};

signed main() {
    //eg
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n1,n2;
    std::string s1,s2;
    std::cin >> n1 >> s1 >> n2 >> s2;
    KMP kmp(s1);//初始化的时候只需要把子串放进去
    auto kk = kmp.match(s2);//再用match匹配函数得到所有的子串，类型是std::vector<int>
    for (auto it : kk) std::cout << it << ' ';
    return 0;
}