KMP

https://oi-wiki.org/string/kmp/

vector<int> get_prefix(string s) {
    int n = s.size();
    vector<int> res(n, 0);
    for (int i = 1; i < n; i++) {
        int j = res[i - 1];
        while (j > 0 && s[i] != s[j]) j = res[j - 1];
        if (s[i] == s[j]) j++;
        res[i] = j;
    }
    return res;
}

vector<int> kmp(string s, string t) {
    string cur = t + "#" + s;
    int n = s.size(), m = t.size();
    vector<int> p = get_prefix(cur);
    vector<int> res;
    for (int i = m; i <= n + m; i++) if (p[i] == m) res.emplace_back(i - m * 2);
    return res;
}