Cod sursa(job #2410007)

Utilizator LucaSeriSeritan Luca LucaSeri Data 19 aprilie 2019 17:15:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX = 4e6 + 10;

int pi[MAX];

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

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	string a, b;
	cin >> a >> b;

	int n = a.size();
	a = '#' + a + '#' + b;

	int cnt = 0;
	vector< int > sol;

	int q = 0;

	for(int i = 2; i < a.size(); ++i) {
		while(q && a[i] != a[q + 1]) q = pi[q];
		if(a[i] == a[q+1]) ++q;

		pi[i] = q;

		if(q == n) {
			++cnt;
			q = pi[q];
			if(cnt <= 1000) sol.emplace_back(i - 2*n - 1);
		}
	}

	cout << cnt << '\n';
	for(auto &x : sol) cout << x << ' ';
	return 0;
}