Cod sursa(job #2922858)

Utilizator apocal1ps13Stefan Oprea Antoniu apocal1ps13 Data 10 septembrie 2022 13:16:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#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;
}