Cod sursa(job #1122195)

Utilizator fhandreiAndrei Hareza fhandrei Data 25 februarie 2014 16:56:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.47 kb
// Include
#include <fstream>
#include <cstring>
using namespace std;

// Constante
const int sz = (int)2e6+2;

// Functii
void makePrefix();

// Variabile
ifstream in("strmatch.in");
ofstream out("strmatch.out");

char str[sz], sub[sz];
int strLen, subLen;

int prefix[sz]; // prefix[i] este lungimea celui mai lung prefix al lui sub[1..i] care este si sufix al lui sub[1..i]

int answer, answers[1001];

// Main
int main()
{
	in >> (sub+1) >> (str+1);
	subLen = strlen(sub+1);
	strLen = strlen(str+1);
	
	// Formez vectorul prefix
	makePrefix();
	
	int currentPrefix = 0;
	
	for(int i=1 ; i<=strLen ; ++i)
	{
		// Atat timp cat lungimea prefixului meu difera de 0, verific daca caracterul de pe pozitia i este
		// acelasi cu cel de pe pozitia currentPrefix+1 (se stie ca, atat timp cat currentPrefix e diferit de 0
		// primele currentPrefix caractere sunt egale)
		while(currentPrefix && sub[currentPrefix+1] != str[i])
			// Ma intorc la cel mai lung prefix-sufix al prefix-sufixului curent
			currentPrefix = prefix[currentPrefix];
		
		// Daca, crescand lungimea prefixului, voi gasi inca o potrivire, il cresc
		if(sub[currentPrefix+1] == str[i])
			++currentPrefix;
		
		// Daca lungimea prefixului este egala cu lungimea subsirului, am gasit inca o potrivire
		if(currentPrefix == subLen)
		{
			if(++answer <= 1000)
				answers[answer] = i-subLen;
			
			// Ma intorc la cel mai lung prefix-sufix al prefix-sufixului curent
			currentPrefix = prefix[currentPrefix];
		}
	}
	
	out << answer << '\n';
	int limit = min(answer, 1000);
	
	for(int i=1 ; i<=limit ; ++i)
		out << answers[i] << ' ';
	
	out << '\n';
	
	in.close();
	out.close();
	return 0;
}

void makePrefix()
{
	int currentPrefix = 0; // Valoarea pe care incerc s-o pun pe pozitia i
	
	for(int i=2 ; i<=subLen ; ++i)
	{
		// Atat timp cat lungimea prefixului meu difera de 0, verific daca caracterul de pe pozitia i este
		// acelasi cu cel de pe pozitia currentPrefix+1 (se stie ca, atat timp cat currentPrefix e diferit de 0
		// primele currentPrefix caractere sunt egale)
		while(currentPrefix && sub[currentPrefix+1] != sub[i])
			// Ma intorc la cel mai lung prefix-sufix al prefix-sufixului curent
			currentPrefix = prefix[currentPrefix];
		
		// Daca, crescand lungimea prefixului, voi gasi inca o potrivire, il cresc
		if(sub[currentPrefix+1] == sub[i])
			++currentPrefix;
		
		// Pun valoarea calculata pe pozitia i
		prefix[i] = currentPrefix;
	}
}