Cod sursa(job #1130485)

Utilizator anaid96Nasue Diana anaid96 Data 28 februarie 2014 13:32:37
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include<stdio.h>
#include<string.h>

using namespace std;

FILE *in,*out;

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

//varibile
char str[sz],sub[sz];
int strLen,subLen;
int strHash1,strHash2;
int subHash1,subHash2;
int baza1=1,baza2=1;
int answer;
int answers[1001];

int main(void)
{
	in=fopen("strmatch.in","rt");
	out=fopen("strmatch.out","wt");
	
	fscanf(in,"%s",sub);
	fscanf(in,"%s",str);
	
	strLen = strlen(str);
	subLen = strlen(sub);
	
	subHash1 = subHash2 = (int) sub[0];
	strHash1 = strHash2 = (int) str[0];
	
	for(int i=1 ; i<subLen ; ++i)
	{
		subHash1 = (subHash1 * baza + sub[i]) % mod1;
		subHash2 = (subHash2 * baza + sub[i]) % mod2;
		strHash1 = (strHash1 * baza + str[i]) % mod1;
		strHash2 = (strHash2 * baza * str[i]) % mod2;
		baza1 = (baza1 * baza) % mod1;
		baza2 = (baza2 * baza) % mod2;
	}
	
	if(subHash1 == strHash1 && subHash2 == strHash2)
		++answer;
	
	for(int i=subLen ; i<strLen ; ++i)
	{
		strHash1 = ((strHash1 - str[i-subLen] * baza1) % mod1) + mod1;
		strHash2 = ((strHash2 - str[i-subLen] * baza2) % mod2) + mod2;
		strHash1 = (strHash1 * baza + str[i]) % mod1;
		strHash2 = (strHash2 * baza + str[i]) % mod2;
		
		if(subHash1 == strHash1 && subHash2 == strHash2)
			if(++answer <= 1000)
				answers[answer]=i - subLen + 1;
	}
	
	fprintf(out,"%d\n",answer);
	
	if(answer<=1000)
		for(int i=1 ; i<= answer ; ++i)
			fprintf(out,"%d ",answers[i]);
	else
		for(int i=1 ; i<=1000 ; ++i)
			fprintf(out,"%d ",answers[i]);	
	
	fclose(in);
	fclose(out);
	return 0;
}