Cod sursa(job #3252704)

Utilizator Cezar2009Cezar Mihai Titihazan Cezar2009 Data 30 octombrie 2024 18:43:43
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 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 d[4000005];
int main()
{
	ios_base::sync_with_stdio(false);
	//cin.tie(NULL);
	string a, b, c;
	int i, j, k, ii, jj, kk, cnt = 0;
	vector <int> rez;

	fin >> a;
	fin >> b;

	c = a + "#" + b;
	//cout << (int)c.size() << "\n\n";

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

	while (c[i] != '#')
	{
		j = i;
		k = 0;
		while (c[j] == c[k])
		{
			++d[i];
			++j;
			++k;
		}
		++i;
	}

	++i;
	while (i < (int)c.size())
	{
		//vad cate sunt egale
		j = i;
		k = 0;
		while ((j < (int)c.size()) && (c[j] == c[k]))
		{
			++d[i];
			++j;
			++k;
		}

		//adaug la rezultat daca e cazul
		if (d[i] == d[0])
		{
			++cnt;
			if (cnt <= 1000)
			{
				rez.push_back(i - (int)a.size() - 1);
			}
		}

		ii = i;
		//ma duc pe cele egale si le pun pe nr defintie
		for (j = ii + 1, k = 1; ((j < (int)c.size()) && (k < d[ii])); ++j, ++k)
		{
			d[j] = min(d[k], ((int)c.size() - ii));
			if (d[j])
			{
				//incerc sa le continui
				jj = j + 1;
				kk = d[j];

				while ((jj < (int)c.size()) && (c[jj] == c[kk]))
				{
					++d[j];
					++jj;
					++kk;
				}
			}

			//adaug la rezultat daca e cazul
			if (d[j] == d[0])
			{
				++cnt;
				if (cnt <= 1000)
				{
					rez.push_back(j - (int)a.size() - 1);
				}
			}
			++i;
		}

		++i;
	}

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

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

	return 0;
}