Cod sursa(job #3357337)

Utilizator iustinola16Olariu Iustin iustinola16 Data 8 iunie 2026 22:30:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>
#include <iostream>
#include <vector>

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

const int NMAX = 4e6 + 5;

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

	string s = a + '#' + b;

	for (int i = 1; i < s.size(); i++) {
		int x = kmp[i - 1];

		while (x > 0 && s[i] != s[x])
			x = kmp[x - 1];

		if (s[i] == s[x])
			x++;

		kmp[i] = x;
	}

	vector<int> ans;
	for (int i = a.size() + 1; i < s.size(); i++) {
		if (kmp[i] == a.size()) {
			int poz = i - 2 * a.size();
			if (ans.size() < 1000)
				ans.push_back(poz);
		}
	}

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

	for (auto it : ans) {
		fout << it << ' ';
	}
	return 0;
}