Cod sursa(job #3252736)

Utilizator Cezar2009Cezar Mihai Titihazan Cezar2009 Data 30 octombrie 2024 20:13:22
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 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");

vector <int> rez;
int d[4000005], cnt;
void adaugRez(int i,int asz)//adaug la rezultat daca e cazul
{
	if (d[i] == d[0])
	{
		++cnt;
		if (cnt <= 1000)
		{
			rez.push_back(i - asz - 1);
		}
	}
}
void verifEgale(int ij, int ik, int i, const string& c)//vad cate sunt egale
{
	int j, k;
	j = ij;
	k = ik;

	while ((j < (int)c.size()) &&(c[j] == c[k]))
	{
		++d[i];
		++j;
		++k;
	}
}
void punSim(int& i, int csz, int asz, const string& c)//ma duc pe cele egale si le pun pe nr defintie
{
	int ii, j, k;
	ii = i;
	for (j = ii + 1, k = 1; ((j < csz) && (k < d[ii])); ++j, ++k)
	{
		d[j] = min(d[k], (csz - j));
		if (d[j])
		{
			verifEgale(j + 1, d[j], j, c);

			adaugRez(j, asz);

			punSim(j, csz, asz, c);
		}
		++i;
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	//cin.tie(NULL);

	string a, b, c;
	int i, j, k, ii;
	

	fin >> a;
	fin >> b;

	c = a + "#" + b;

	i = 1;
	d[0] = (int)a.size();

	while (c[i] != '#')
	{
		verifEgale(i, 0, i, c);
		++i;
	}

	++i;
	while (i < (int)c.size())
	{
		verifEgale(i, 0, i, c);

		adaugRez(i, (int)a.size());

		punSim(i, (int)c.size(), (int)a.size(), c);

		++i;
	}

	/*for (i = 0; i < c.size(); ++i)
	{
		cout << d[i] << " ";
	}*/

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

	return 0;
}