Cod sursa(job #773846)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 2 august 2012 18:17:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <string.h>
#define MAX 2000001
#define P 73
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[MAX], b[MAX], s[MAX];
int na, nb, ha1, ha2, p1, p2, hb1, hb2, i, nr;
int main()
{
	f.get(a, MAX);
	f.get();
	f.get(b, MAX);
	f.get();
	f.close();
	na=strlen(a);
	nb=strlen(b);
	p1=p2=1;
	ha1=ha2=0;
	for(i=0; i<na; i++)
	{
		ha1=(ha1*P+a[i])%MOD1;
		ha2=(ha2*P+a[i])%MOD2;
		if (i!=0)
			p1=(p1*P)%MOD1,
			p2=(p2*P)%MOD2;
	}
	if(na>nb)
	{
		g<<"0\n";
		return 0;
	}
	for(i=0; i<na; i++)
	{
		hb1=(hb1*P+b[i])%MOD1;
		hb2=(hb2*P+b[i])%MOD2;
	}
	if(hb1==ha1 && hb2==ha2)
	{
		s[0]=1;
		nr++;
	}
	for(i=na; i<nb; i++)
	{
		hb1=((hb1-(b[i-na]*p1)%MOD1+MOD1)*P+b[i])% MOD1;
		hb2=((hb2-(b[i-na]*p2)%MOD2+MOD2)*P+b[i])% MOD2;
		if(hb1==ha1 && hb2==ha2)
		{
			s[i-na+1]=1;
			nr++;
		}
	}
	g<<nr<<"\n";
	nr=0;
	for(i=0; i<nb && nr<1000; i++)
		if(s[i])
		{
			nr++;
			g<<i<<' ';
		}
	g<<"\n";
	return 0;
}