Cod sursa(job #3357599)

Utilizator iustinola16Olariu Iustin iustinola16 Data 11 iunie 2026 20:31:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int NMAX = 4e6 + 5;

int z[NMAX];
int main() {
	string a, b;
	fin >> a >> b;

	string s = a + "#" + b;
	int n = s.size();

	int l = 0, r = 0;
	for (int i = 1; i < n; i++) {
		if (i < r)
			z[i] = min(r - i, z[i - l]);

		while (i + z[i] < n && s[z[i]] == s[i + z[i]])
			z[i]++;

		if (i + z[i] > r) {
			l = i;
			r = i + z[i];
		}
	}

	vector<int> ans;
	for (int i = a.size() + 1; i < n; i++) {
		if (z[i] >= a.size())
			ans.push_back(i - a.size() - 1);
	}

	fout << ans.size() << '\n';

	for (int i = 0; i < min((int)ans.size(), 1000); i++) {
		fout << ans[i] << ' ';
	}
	return 0;
}