Cod sursa(job #820212)

Utilizator cristi_berceanuFMI - Cristi Berceanu cristi_berceanu Data 20 noiembrie 2012 14:39:19
Problema Potrivirea sirurilor Scor 86
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<cstdio>
#include<string.h>
#define p 73
#define mod1 100007
#define mod2 100021
#define maxn 2000010

char s[maxn],t[maxn];
int m[maxn],ct;
int hs1,hs2,ht1,ht2,p1,p2,i,ns,nt;
void citire()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",&s,&t);

ns=strlen(s);
nt=strlen(t);
}

void first_word_hash()
{
p1=p2=1;
for(i=0;i<ns;i++)
{
hs1=(hs1*p+s[i])%mod1;
hs2=(hs2*p+s[i])%mod2;

if(i!=0)
	{
		p1=(p*p1)%mod1;
		p2=(p*p2)%mod2;
	}
}	


}
int main()
{
citire();
first_word_hash();

if(strlen(s)>strlen(t))
{
	printf("\n");
	return 0;
}

for(i=0;i<ns;i++)
{
	ht1=(ht1*p+t[i])%mod1;
	ht2=(ht2*p+t[i])%mod2;

}



if(ht1==hs1&&ht2==hs2)
{
m[0]=1; ct++;
}

for(i=ns;i<nt;i++)
{
ht1=((ht1-(t[i-ns]*p1)%mod1+mod1)*p+t[i])%mod1;
ht2=((ht2-(t[i-ns]*p2)%mod2+mod2)*p+t[i])%mod2;

if(ht1==hs1&&ht2==hs2)
{
	m[i-ns+1]=1; ct++;
}

}
printf("%d\n",ct);
ct=0;


for(i=0;i<nt&&ct<1000;i++)
{
if(m[i]==1) {ct++; printf("%d ",i);}
}
return 0;
}