Cod sursa(job #565864)

Utilizator gabriel93Robu Gabriel gabriel93 Data 28 martie 2011 13:02:14
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<fstream>
#include<iostream>
#include<string.h>
using namespace std;
fstream f1,f2;
char a[2000002],b[2000002],match[2000002];
int na,nb,i,p1,p2,p,mod1,mod2,nr1,hasha1,hasha2,hash1,hash2;
int main()
{
p=73;
mod1=1007;
mod2=1021;
f1.open("strmatch.in",ios::in);
f2.open("strmatch.out",ios::out);
f1>>a>>b;
na=strlen(a);
nb=strlen(b);
if(na>nb)
	cout<<"0";
p1=p2=1;
hasha1=hasha2=0;
for(i=0;i<na;i++)
{
	hasha1=(hasha1*p+a[i])%mod1;
	hasha2=(hasha2*p+a[i])%mod2;
	if(i!=0)
	{
		p1=p1*p%mod1;
		p2=p2*p%mod2;
	}
}
hash1=hash2=0;
for(i=0;i<na;i++)
{
	hash1=(hash1*p+b[i])%mod1;
	hash2=(hash2*p+b[i])%mod2;
}
nr1=0;
if(hash1==hasha1&&hash2==hasha2)
{
	match[0]=1; 
	nr1++;
}
for(i=na;i<nb;i++)
{
	hash1=((hash1-(b[i-na]*p1)%mod1+mod1)*p+b[i])%mod1;
	hash2=((hash2-(b[i-na]*p2)%mod2+mod2)*p+b[i])%mod2;
	if(hash1==hasha1&&hash2==hasha2)
	{
		match[i-na+1]=1;
		nr1++;
	}
}
cout<<nr1<<"\n";
nr1=0;
for(i=0;i<nb&&nr1<1000;i++)
	if(match[i])
		cout<<i<<" ";
f1.close();
f2.close();
return 0;
}