Cod sursa(job #3252700)

Utilizator Cezar2009Cezar Mihai Titihazan Cezar2009 Data 30 octombrie 2024 18:40:12
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
//https://infoarena.ro/problema/strmatch 80p
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("fast-math")
#pragma GCC optimize ("unroll-loops")
#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, cnt = 0;
	vector <int> rez;

	fin >> a;
	fin >> b;

	c = a + "#" + b;
	//cout << c;

	i = 1;
	d[0] = a.size();
	//cout << d[0] << " ";

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

		//cout << d[i] << " ";
		++i;
	}

	++i;
	while (i < c.size())
	{
		j = i;
		k = 0;
		while (c[j] == c[k])
		{
			++d[i];
			++j;
			++k;
		}

		//cout << d[i] << " ";
		if (d[i] == d[0])
		{
			//fout << i - a.size() - 1 << " ";
			++cnt;

			if (cnt <= 1000)
			{
				rez.push_back(i - a.size() - 1);
			}
		}
		++i;
	}

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