Cod sursa(job #2293332)

Utilizator dey44andIoja Andrei-Iosif dey44and Data 30 noiembrie 2018 21:12:32
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 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];

int Min(int a, int b)
{
	return a < b ? a : b;
}

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)
		{
				positions.push_back(i - pivot);
			pivot = urmator[pivot];
		}
	}
}

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

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