Cod sursa(job #3253488)

Utilizator Cezar2009Cezar Mihai Titihazan Cezar2009 Data 2 noiembrie 2024 21:41:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
//https://infoarena.ro/problema/strmatch
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("fast-math")
//#pragma GCC optimize ("unroll-loops")
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

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

int main()
{
	ios_base::sync_with_stdio(false);
	//cin.tie(NULL);

	string a, b, c, d;
	vector <int> sf(2000005, 0);
	vector <int> rez;
	int i, j, cnt = 0;

	fin >> a;
	fin >> b;
	a = '0' + a;
	b = '0' + b;
	//cout << a << " " << b << "\n";

	for (i = 2, j = 0; i < (int)a.size(); ++i)
	{
		while (j && (a[j + 1] != a[i]))
		{
			j = sf[j];
		}

		//cout << a[i] << " " << a[j + 1] << "\n";
		if (a[i] == a[j + 1])
		{
			++j;
		}

		sf[i] = j;
		//cout << i << " " << j << "\n";
	}

	/*for (i = 0; i < a.size(); ++i)
	{
		cout << sf[i] << " ";
	}
	cout << "\n";*/

	for (i = 1, j = 0; i < (int)b.size(); ++i)
	{
		while ((j != 0) && (a[j + 1] != b[i]))
		{
			j = sf[j];
		}

		if (b[i] == a[j + 1])
		{
			++j;
		}

		//cout << j << " ";
		if (j == ((int)a.size() - 1))
		{
			++cnt;
			if (cnt <= 1000)
			{
				rez.push_back(i - (int)a.size() + 1);
			}
			j = sf[j];
		}
	}

	fout << cnt << "\n";
	for (auto x : rez)
	{
		fout << x << " ";
	}


	return 0;
}