模板题: P3375 【模板】KMP字符串匹配
#include <bits/stdc++.h>
using namespace std;
struct KMP {
const int n;
string p;
vector<int> nxt;
KMP(string p) : n(p.size()), p(p), nxt(n + 1) {
for (int i = 1, j = 0; i < n; ++ i) {
while (j > 0 && p[i] != p[j]) {
j = nxt[j];
}
if (p[i] == p[j]) {
j ++;
}
nxt[i + 1] = j;
}
}
int operator[] (const int x) const { return nxt[x + 1]; }
vector<int> match(string &s) {
vector<int> pos;
for (int i = 0, j = 0; i < s.size(); ++ i) {
while (j > 0 && s[i] != p[j]) {
j = nxt[j];
}
if (s[i] == p[j]) {
j ++;
}
if (j == n) {
pos.push_back(i - n + 1);
j = nxt[j];
}
}
return pos;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s, p;
cin >> s >> p;
//预处理
KMP f(p);
//匹配
auto res = f.match(s);
//输出所有匹配位置
for (auto x : res) {
cout << x + 1 << "\n";
}
//输出border
for (int i = 0; i < p.size(); ++ i) {
cout << f[i] << " ";
}
return 0;
}