Cod sursa(job #2303182)

Utilizator dey44andIoja Andrei-Iosif dey44and Data 15 decembrie 2018 19:30:41
Problema Potrivirea sirurilor Scor 24
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 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 > -1 && pattern[pivot + 1] != pattern[i]) pivot = urmator[pivot];
		if (pattern[pivot + 1] == pattern[i]) pivot++;
		urmator[i] = pivot;
	}
}
 
void String_Match()
{
	urmator[0] = -1;
	int pivot = -1;
	for (unsigned i = 0; i < model.size(); i++)
	{
		while (pivot > -1 && 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;
}