Cod sursa(job #1122018)

Utilizator fhandreiAndrei Hareza fhandrei Data 25 februarie 2014 15:23:53
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.27 kb
// Include
#include <fstream>
using namespace std;

// Constante
const int sz = (int)2e6+1;
const int base = 73;
const int mod1 = 20007; // Toate variabilele ce se termina cu 1 vor fi facute % mod1
const int mod2 = 20021; // Toate variabilele ce se termina cu 2 vor fi facute % mod2

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

char str[sz], sub[sz];
int strLen, subLen;
int hash1, hash2; // Valoarea asociata sirului sub
int current1, current2; // Valoarea asociata subsirului din str verificat in momentul curent
int base1=1, base2=1; // base la puterea subLen-1 % mod

int answer, answers[1001];

// Main
int main()
{
	in >> sub >> str;
	strLen = strlen(str);
	subLen = strlen(sub);
	
	// Initial, hash va contine primul caracter al lui sub, iar current va contine primul caracter al lui str
	hash1 = hash2 = sub[0];
	current1 = current2 = str[0];
	
	for(int i=1 ; i<subLen ; ++i)
	{
		hash1 = (hash1 * base + sub[i]) % mod1;
		hash2 = (hash2 * base + sub[i]) % mod2;
		
		current1 = (current1 * base + str[i]) % mod1;
		current2 = (current2 * base + str[i]) % mod2;
		
		base1 = (base1*base) % mod1;
		base2 = (base2*base) % mod2;
	}
	
	// Am terminat de parcurs sirul sub. Simultan, current contine valoarea asociata subsirului str[0..subLen)
	// Verific daca cele doua siruri precizate anterior sunt egale
	if(hash1 == current1 && hash2 == current2)
		++answer;
	
	
	// Iau toate subsirurile de lungime subLen ale lui str
	for(int i=subLen ; i<strLen ; ++i)
	{
		// Elimin valoarea asociata primei litere din variabila current
		// Diferenta imi va da ceva negativ. Astfel, adaug mod pentru a-l readuce la pozitiv
		current1 = (current1 - str[i-subLen]*base1) % mod1 + mod1;
		current2 = (current2 - str[i-subLen]*base2) % mod2 + mod2;
		
		// Adaug o noua litera
		current1 = (current1 * base + str[i]) % mod1;
		current2 = (current2 * base + str[i]) % mod2;
		
		// Verific daca subsirul nou-format este acelasi cu sub
		if(hash1 == current1 && hash2 == current2)
			if(++answer <= 1000)
				answers[answer] = i-subLen+1;
	}
	
	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;
}