Cod sursa(job #1131026)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 28 februarie 2014 17:18:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include<fstream>
#include<vector>
#include<string.h>

using namespace std;

#define max_n 2000010
#define base 73
#define mod1 100007
#define mod2 100021
#define s_max 1000

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

int L , LB , p1 , p2 , nr;
int hashA1 , hashA2 , hashB1 , hashB2;
char s1[max_n] , s2[max_n];

vector<int>Sol;

void read(){
	
	f>>s1>>s2;
	L = strlen(s1);
	LB = strlen(s2);
}

long long power( int a , int b , int mod ){
	if( b == 0 )
		return 1;
	int p = power(a , b / 2 , mod);
	if( b % 2 == 1 )
		return ((((long long)p * p) % mod) * a) % mod;
	else
		return ((long long)p * p) % mod;
}

int main(){
	
	read();
	
	if( L > LB )
		goto end;
	
	p1 = power(base , L - 1 , mod1);
	p2 = power(base , L - 1 , mod2);
	
	for( int i = 0 ; i < L ; i++ ){
		hashA1 = (hashA1 * base + s1[i]) % mod1;
		hashA2 = (hashA2 * base + s1[i]) % mod2;
	}
	
	for( int i = 0 ; i < L ; i++ ){
		hashB1 = (hashB1 * base + s2[i]) % mod1;
		hashB2 = (hashB2 * base + s2[i]) % mod2;
	}
	
	if( hashB1 == hashA1 && hashB2 == hashA2 ){
		Sol.push_back(0);
		nr++;
	}
	
	for( int i = L ; i < LB ; i++ ){
		hashB1 = (((( hashB1 - p1 * s2[i-L] ) % mod1) + mod1) * base + s2[i]) % mod1;
		hashB2 = (((( hashB2 - p2 * s2[i-L] ) % mod2) + mod2) * base + s2[i]) % mod2;
		if( hashB1 == hashA1 && hashB2 == hashA2 ){
			if( Sol.size() < s_max )
				Sol.push_back(i - L + 1);
			nr++;
		}
	}
	
	end:
	
	g<<nr<<"\n";
	for( unsigned int i = 0 ; i < Sol.size() ; i++ )
		g<<Sol[i]<<" ";
	
	return 0;
}