Cod sursa(job #1090959)

Utilizator fhandreiAndrei Hareza fhandrei Data 23 ianuarie 2014 12:34:07
Problema Potrivirea sirurilor Scor 28
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
// Include
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

// Constante
const int sz = (int)2e6+1;
const int mod1 = 20007;
const int mod2 = 20021;
const int base = 73;

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

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

int current1, current2;
int hash1, hash2;
int base1=1, base2=1;

int answer;
int answers[1001];

// Main
int main()
{
	in >> sub >> str;
	subLen = strlen(sub);
	strLen = strlen(str);
	
	hash1 = hash2 = (int)sub[0] % base;
	current1 = current2 = (int)str[0] % base;
	
	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;
	}
	
	if(hash1 == current1 && hash2 == current2)
		answers[answer=1] = 0;
	
	for(int i=subLen ; i<strLen ; ++i)
	{
		current1 = ((current1 - str[i-subLen]*base1) % mod1) + mod1;
		current1 = (current1*base + str[i]) % mod1;
		
		current2 = ((current2 - str[i-subLen]*base2) % mod2) + mod2;
		current2 = (current2*base + str[i]) % mod2;
		
		if(hash1 == current1 && hash2 == current2)
		{
			if(++answer <=1000)
				answers[answer] = i - subLen + 1;
		}
	}
	
	out << answer << '\n';
	int limit = min(1000, answer);
	for(int i=1 ; i<=limit ; ++i)
		out << answers[i] << ' ';
	
	out << '\n';
	
	in.close();
	out.close();
	return 0;
}