Cod sursa(job #3147864)

Utilizator daristyleBejan Darius-Ramon daristyle Data 27 august 2023 17:47:10
Problema Potrivirea sirurilor Scor 28
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>

using namespace std;

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

const int STRLEN_MAX = 2e6;
const char SANTINELA = '&';
const int POS_MAX = 1e3;
char str[STRLEN_MAX + 2], pattern[STRLEN_MAX + 1];
int z[STRLEN_MAX];
int pos[POS_MAX];

int strlen(const char* str){
	int len = 0;
	while(str[len])
		++len;

	return len;
}

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

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

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

		++i;
	}
}

int ZAlgorithm(const char* pattern, char* str){
	int pattern_len = strlen(pattern);
	int str_len = strlen(str);

	str[str_len] = SANTINELA;
	str[str_len + 1] = '\0';

	ComputeZFunction(pattern, str);

	str[str_len] = '\0';

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

		++i;
	}

	return matches;
}

int main(){
	fin >> pattern >> str;

	int matches = ZAlgorithm(pattern, str);

	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;
}