Cod sursa(job #629624)

Utilizator cremarencodianaCremarenco Diana cremarencodiana Data 3 noiembrie 2011 16:20:01
Problema Potrivirea sirurilor Scor 86
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
# include <fstream>
# include<string>
using namespace std;
int hash11, hash12, hash21, hash22,na,nb,p1,p2,i,nr,sol[2000001];
string a,b;
int main()
{
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f>>a;
	f>>b;
	p1=p2=1;
	hash11=hash12=hash21=hash22=0;
	na=a.length();
	nb=b.length();
	for (i=0; i<na; i++)
	{
		hash11=(hash11*73+a[i]) % 100021;
		hash12=(hash12*73+a[i]) % 100007;
		if (i!=0)
		{
			p1=(p1*73)%100021;
			p2=(p2*73)%100007;
		}
	}
	if (na>nb) { printf("0\n"); return 0;}
	for (i=0; i<na; i++)
	{
		hash21=(hash21*73+b[i])% 100021;
		hash22=(hash22*73+b[i])% 100007;
	}
	nr=0;
	if (hash11==hash21 && hash12==hash22)
		{sol[0]=1; nr++;}
	for (i=na; i<nb; i++)
	{
		hash21=((hash21-(b[i-na]*p1)% 100021+100021)*73+b[i])%100021;
		hash22=((hash22-(b[i-na]*p2)% 100007+100007)*73+b[i])%100007;
		if (hash11==hash21 && hash12==hash22) {sol[i-na+1]=1; nr++;}
	}
	g<<nr<<"\n";
		nr=0;
	for (i=0; i<=nb && nr<1000; i++)
		if (sol[i])
		{
			nr++;
		g<<i<<" ";
		}
	g<<"\n";
	return 0;
}