Cod sursa(job #574985)

Utilizator Robert29FMI Tilica Robert Robert29 Data 7 aprilie 2011 19:13:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<stdio.h>
#include<string.h>
#define b 73
#define mod1 100007
#define mod2 100021
FILE*f=fopen("strmatch.in","r");
FILE*g=fopen("strmatch.out","w");
int n,i,j,p1,p2,h1,h2,ha1,ha2,nr,x,y,sol[1001];
char v[2000001],w[2000001];
int main() {
	fscanf(f,"%s\n",v);
	fscanf(f,"%s",w);

	x=strlen(v);
	y=strlen(w);
	
	for(i=0;i<x;++i){
		ha1=(ha1*b+v[i])%mod1;
		ha2=(ha2*b+v[i])%mod2;	
	}
	
	for(i=0;i<x;++i){
		h1=(h1*b+w[i])%mod1;
		h2=(h2*b+w[i])%mod2;	
	}
	
	if(h1==ha1&&h2==ha2)
		sol[++nr]=0;
	
	p1=p2=1;
	for(i=1;i<x;++i){
		p1=p1*b%mod1;
		p2=p2*b%mod2;
	}
	
	for(i=x;i<y;++i){
		h1=((h1-(w[i-x]*p1)%mod1+mod1)*b+w[i])%mod1;
		h2=((h2-(w[i-x]*p2)%mod2+mod2)*b+w[i])%mod2;
		
		if(h1==ha1&&h2==ha2)
			if(nr<1000)
				sol[++nr]=i-x+1;
			else
				++nr;
	}
	
	fprintf(g,"%d\n",nr);
	if(nr>1000)
		nr=1000;
	for(i=1;i<=nr;++i)
		fprintf(g,"%d ",sol[i]);
	
	fclose(g);
	fclose(f);
	return 0;
}