Cod sursa(job #2293330)

Utilizator dey44andIoja Andrei-Iosif dey44and Data 30 noiembrie 2018 21:06:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <vector>
#include <string>

#define input "strmatch.in"
#define output "strmatch.out"
#define NMAX 2000005

using namespace std;

ifstream in(input);
ofstream out(output);

vector < int > positions;
string model, pattern;
int urmator[NMAX];

void Read_Data()
{
	in >> pattern >> model;
}

void Prefix()
{
	int pivot = -1;
	for (unsigned i = 1; i < pattern.size(); i++)
	{
		while (pivot > 0 && pattern[pivot + 1] != pattern[i]) pivot = urmator[pivot];
		if (pattern[pivot + 1] == pattern[i]) pivot++;
		urmator[i] = pivot;
	}
}

void String_Match()
{
	int pivot = -1;
	for (unsigned i = 0; i < model.size(); i++)
	{
		while (pivot > 0 && pattern[pivot + 1] != model[i]) pivot = urmator[pivot];
		if (pattern[pivot + 1] == model[i]) pivot++;
		if (pivot == pattern.size() - 1)
		{
			if (positions.size() < 1000)
				positions.push_back(i - pivot);
			else break;
			pivot = urmator[pivot];
		}
	}
}

void Print_Sol()
{
	out << positions.size() << "\n";
	for (unsigned i = 0; i < positions.size(); i++)
		out << positions[i] << " ";
}

int main()
{
	Read_Data();
	Prefix();
	String_Match();
	Print_Sol();
	return 0;
}