Pagini recente » Cod sursa (job #13551) | Cod sursa (job #3251360) | Cod sursa (job #135903) | Cod sursa (job #1087899) | Cod sursa (job #2803427)
#include <bits/stdc++.h>
std::ifstream in("strmatch.in");
std::ofstream out("strmatch.out");
std::vector<int> kmp(const std::string &s) {
std::vector<int> pi(s.size());
pi[0] = 0;
for (int i = 1; i < int(s.size()); ++i) {
int last = pi[i - 1];
while(last != 0 && s[i] != s[last]) {
last = pi[last - 1];
}
if (s[i] != s[last]) {
last = -1;
}
pi[i] = last + 1;
}
return pi;
}
int main() {
std::string a, b;
in >> a >> b;
auto pi = kmp(a + "#" + b);
auto start = pi.begin() + a.size() + 1;
out << std::count(start, pi.end(), a.size()) << "\n";
for (auto it = start; it != pi.end(); ++it) {
if (*it == int(a.size())) {
out << it - start - a.size() + 1 << " ";
}
}
out << "\n";
}