Cod sursa(job #3230640)

Utilizator ClassicalClassical Classical Data 22 mai 2024 08:20:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef INFOARENA
	freopen ("strmatch.in", "r", stdin);
	freopen ("strmatch.out", "w", stdout);
#endif

	string pat, txt;
	cin >> pat >> txt;
	
	int sub = (int) pat.size();
	
	pat += "$" + txt;
	
	vector<int> ps((int)pat.size(), 0);
	
	for (int i = 1; i < (int) pat.size(); i++) {
		ps[i] = ps[i - 1];
		while (ps[i] > 0 && pat[i] != pat[ps[i]]) {
			ps[i] = ps[ps[i] - 1];
		}
		if (pat[i] == pat[ps[i]]) {
			ps[i]++;
		}
	}
	vector<int> sol;
	for (int i = sub; i < (int) pat.size(); i++) {
		if (ps[i] == sub) {
			sol.push_back(i - 2 * sub);
		}
	}
	cout << (int) sol.size() << "\n";
	if ((int) sol.size() > 1000) {
		sol.resize(1000);
	}	
	for (auto &i : sol) {
		cout << i << " ";
	}
	cout << "\n";
	return 0;
}