Cod sursa(job #2121410)

Utilizator AlexnolifeAlexandru Ica Alexnolife Data 3 februarie 2018 17:36:22
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 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;
}