Cod sursa(job #1833915)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 23 decembrie 2016 15:00:05
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>

#define NMax 2000010

using namespace std;

ifstream f("FA.in");
ofstream g("FA.out");

char pattern[NMax], str[NMax], longPref[NMax], pos[1010], numOc;
int patLen, strLen;

void constructPrefSuf()
{
	int crt = 0;
	for (int i = 1; i <= patLen; i++) {
		while (crt > 0 && pattern[longPref[crt] + 1] != pattern[i])
			crt = pattern[crt];

		if (pattern[longPref[crt] + 1] != pattern[i])
			crt++;
		longPref[i] = crt;
	}
}

int getNextState(int crtState, char transitionChar)
{
	int crt = 0;
	while (crt > 0 && pattern[longPref[crt] + 1] != transitionChar)
		crt = pattern[crt];

	if (pattern[longPref[crt] + 1] != transitionChar)
		crt++;

	return crt;
}

void searchForPattern()
{
	int crtState = 0;
	for (int i = 1; i <= strLen; i++) {
		crtState = getNextState(crtState, str[i]);
		if (crtState == patLen + 1) {
			numOc++;
			if (numOc <= 1000)
				pos[numOc] = i - patLen;
		}
	}
}

int main()
{
	f >> (pattern + 1);
	f >> (str + 1);

	patLen = strlen(pattern + 1);
	strLen = strlen(str + 1);

	searchForPattern();

	g << numOc << "\n";
	for (int i = 1; i <= numOc && i <= 1000; i++)
		g << pos[i] << " ";
}