kmp.cpp
struct KMP {
const int n;
const string s;
vector<int> f;
KMP(const string &str) : n(str.size()), s(str), f(n, 0) {
int k = 0;
for (int i = 1; i < n; ++i) {
while (k > 0 && s[k] != s[i]) k = f[k - 1];
if (s[k] == s[i]) ++k;
f[i] = k;
}
}
vector<int> query(const string &t) {
int k = 0;
vector<int> res;
for (int i = 0; i < (int)t.size(); ++i) {
while (k == n || (k > 0 && s[k] != t[i])) k = f[k - 1];
if (s[k] == t[i]) ++k;
res.push_back(k);
}
return res;
}
};