Cod sursa(job #3147828)

Utilizator daristyleBejan Darius-Ramon daristyle Data 27 august 2023 14:17:12
Problema Potrivirea sirurilor Scor 34
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int STRLEN_MAX = 2e5;
const char SEPARATOR = '&';
const int POS_MAX = 1e3;
char str[2 * STRLEN_MAX + 2];
char aux[STRLEN_MAX];
int z[2 * STRLEN_MAX + 1];
int pos[POS_MAX];

int ZRead(){
	fin >> str;

	int pattern_length = 0;
	while(str[pattern_length])
		++pattern_length;

	str[pattern_length] = SEPARATOR;

	fin >> aux;

	int i = 0;
	while(aux[i]){
		str[i + pattern_length + 1] = aux[i];
		++i;
	}
	str[i + pattern_length + 1] = '\0';

	return pattern_length;
}

void ComputeZFunction(){
	int left = 0, right = 0, i = 1;
	z[0] = 0;
	while(str[i]){
		if(i <= right)
			z[i] = min(z[i - left], right - i + 1);
		else
			z[i] = 0;

		while(str[z[i]] == str[i + z[i]])
			++z[i];

		if(i + z[i] > right){
			right = i + z[i];
			left = i;
		}

		++i;
	}
}

int ZAlgorithm(){
	int pattern_len = ZRead();

	ComputeZFunction();

	int i = 0, matches = 0;
	while(str[i]){
		if(z[i] == pattern_len){
			if(matches < POS_MAX)
				pos[matches] = i - pattern_len - 1;
			++matches;
		}

		++i;
	}

	return matches;
}

int main(){
	int matches = ZAlgorithm();

	fout << matches << '\n';
	if(matches > POS_MAX)
		matches = POS_MAX;
	for(int i = 0; i < matches; ++i)
		fout << pos[i] << ' ';
	fout.put('\n');

	fin.close();
	fout.close();
	return 0;
}