算法
(MP) $O(N)$
算法竞赛里的 kmp
其实是 mp
,因为没有用到 $Knuth$ 提到的优化
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
// Morris-Pratt
template<typename T>
struct MP {
int n;
T t;
vector<int> a;
MP() {}
MP(const T& t): t(t) {
n = t.size();
a = vector<int>(n+1);
a[0] = -1;
int j = -1;
rep(i, n) {
while (j != -1 and t[j] != t[i]) j = a[j];
j++;
a[i+1] = j;
}
}
int operator[](int i) { return a[i]; }
vector<int> findAll(const T& s) {
vector<int> res;
int j = 0;
for (int i = 0; i < s.size(); ++i) {
while (j != -1 and t[j] != s[i]) j = a[j];
j++;
if (j == n) {
res.push_back(i-j+1);
j = a[j];
}
}
return res;
}
};
int main() {
string s1, s2;
cin >> s1 >> s2;
MP<string> mp(s2);
auto ans = mp.findAll(s1);
for (int x : ans) {
cout << x+1 << '\n';
}
for (int i = 1; i <= int(s2.size()); ++i) cout << mp[i] << ' ';
return 0;
}