Cod sursa(job #2115573)

Utilizator AlexnolifeAlexandru Ica Alexnolife Data 26 ianuarie 2018 21:38:07
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>

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

char substring[2000000], fullstring[2000000];
int i = 0, j = 1;
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 && substring[j] != NULL) {
		if (substring[i] == substring[j]) {
			auxArray[j] = i + 1;

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

	length = j;
}

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

	bool pattern = false;

	for (i = 0; fullstring[i] != NULL; i++) {
		
		if (fullstring[i] == substring[offset]) {

			pattern = true;

			if (offset == length - 1) {
				nrap++;

				if(index < 1000) values[index++] = i - length + 1;

				offset = auxArray[offset];
			}
			else {
				offset++;
			}
		}
		else {
			if (pattern) i--;
			pattern = false;

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

	g << nrap << "\n";

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

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