Pagini recente » Cod sursa (job #1809386) | Cod sursa (job #260077) | Cod sursa (job #971352) | Cod sursa (job #1757652) | Cod sursa (job #2922858)
#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;
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();
vector <int> ans;
for (int i = 0; i < s.size(); i++) {
if (kmp[i] >= c.size()) {
ans.push_back(i - 2 * c.size());
}
}
out << ans.size() << '\n';
for (int i = 0; i < min((int)ans.size(), 1000); i++) {
out << ans[i] << ' ';
}
return 0;
}