KMP算法

字符串还是太难了stO.
KMP模板题：https://www.luogu.com.cn/problem/P3375

#include <bits/stdc++.h>
using namespace std;
struct KMP {
    string s, t;      // t为模式串
    vector<int> nxt;  // nxt[i]表示t的长度为i的前缀（或者说t[i]之前的字符组成的字串）的border的最长长度
    KMP(string s, string t) : s(s), t(t), nxt(t.size()+1) {}
    auto init() {
        int len = t.size(), i = 0, j = -1;
        nxt[0] = -1;
        while (i < len) {
            if (j == -1 || t[i] == t[j]) {
                i++, j++;
                nxt[i] = j;
            } else {
                j = nxt[j];
            }
        }
        return nxt;
    }
    auto run() {
        int si = 0, ti = 0, slen = s.size(), tlen = t.size();
        vector<int> res;  // 存匹配位置的起始下标
        while (si < slen && ti < tlen) {
            if (ti == -1 || s[si] == t[ti]) {
                si++, ti++;
            } else {
                ti = nxt[ti];
            }
            if (ti == tlen) {              // 说明tlen-1与si-1成功匹配，即整个串成功匹配
                res.push_back(si - tlen);  // 最后匹配到的是si-1,那起始下标就是si-tlen
                ti = nxt[ti];              // 继续匹配，从已匹配部分的最长border开始
            }
        }
        // for (auto &i : res) cout << i + 1 << "\n";
        // for (int i = 1; i <= tlen; i++) cout << nxt[i] << " ";
        return res;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s, t;
    cin >> s >> t;
    KMP kmp(s, t);
    auto nxt=kmp.init();
    auto res=kmp.run();
    for (auto &i : res) cout << i + 1 << "\n";
    for (int i = 1; i < nxt.size(); i++) cout << nxt[i] << " ";
    return 0;
}