Cod sursa(job #2147356)

Utilizator AlexnolifeAlexandru Ica Alexnolife Data 28 februarie 2018 17:58:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>

std::ofstream g("strmatch.out");

char substring[2000000], fullstring[2000000];
int i = 1, j = 0;
int length = 0;
int auxArray[2000000]; 

int values[1000];
int index = 0;

void Read()
{
	std::ifstream f("strmatch.in");

	f >> substring;
	f >> fullstring;
}

void CompleteAuxArray()
{
	while (substring[i] != NULL) {		
		if (substring[i] == substring[j]) {	
			auxArray[i] = j + 1;
			
			++i;
			++j;
		}
		else if (j > 0) {
			j = auxArray[j - 1];
		}
		else {	
			auxArray[i] = 0;	
			++i;
		}
	}

	length = i;
}

void Substr()
{
	int offset = 0;
	int nrap = 0;

	for (i = 0; fullstring[i] != NULL;) {	
		if (fullstring[i] == substring[offset] && offset == length - 1) {
			nrap++;
			
			if (index < 1000) {
				values[index++] = i - offset;
			}

			if (offset > 0) {
				offset = auxArray[offset - 1];
			}
		}
		else if (fullstring[i] == substring[offset]) {
			++i;
			++offset;
		}
		else if (offset > 0) {
			offset = auxArray[offset - 1];
		}
		else {
			i++;
		}
		
	}

	g << nrap << "\n";

	for (int k = 0; k < index; k++) {
		g << values[k] << " ";
	}

	g << "\n";
}

int main()
{
	Read();
	CompleteAuxArray();
	Substr();

	return 0;
}