Pagini recente » Cod sursa (job #971518) | Cod sursa (job #2908071) | Cod sursa (job #1645278) | Cod sursa (job #1472649) | Cod sursa (job #2922856)
#include<iostream>
#include<fstream>
#include<unordered_map>
#include<string>
#include<vector>
std::ifstream in("strmatch.in");
std::ofstream out("strmatch.out");
using namespace std;
int kmp[4000001];
string s, c;
vector<int>v;
void calc() {
int last = 0;
for (int i = 1; i < s.size(); i++) {
last = i - 1;
while (last >= 1 && s[i] != s[kmp[last]]) {
last = kmp[last] - 1;
}
if (s[i] == s[kmp[last]]) kmp[i] = kmp[last] + 1;
}
}
int main() {
ios_base::sync_with_stdio(false);
in.tie(nullptr);
out.tie(nullptr);
in >> c >> s;
s = c + '$' + s + '0';
calc();
for (int i = 0; i < s.size(); i++)
if (kmp[i] >= c.size()) v.push_back(i - 2 * c.size());
out << v.size() << '\n';
for (auto i : v) out << i << " ";
return 0;
}