Cod sursa(job #2115542)

Utilizator AlexnolifeAlexandru Ica Alexnolife Data 26 ianuarie 2018 21:11:56
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>

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

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

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) {
				offset = 0;
				nrap++;
			}
			else {
				offset++;
			}
		}
		else {
			if (pattern) {
				if (offset >= 1) {
					offset = auxArray[offset - 1];
				}
				else offset = 0;

				pattern = false;
				i--;
			}
		}
	}

	g << nrap << "\n";
}

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