Cod sursa(job #1076192)

Utilizator alexsuciuAlex Suciu alexsuciu Data 9 ianuarie 2014 22:40:21
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<fstream>
#include<cstring>
#include<iostream>
#define mod1 100007
#define mod2 100021
using namespace std;

char a[20000002],b[20000002];
long n,m,i,v[1001],nr;

long ha1,ha2,hb1,hb2;
long h1=1,h2=1;

int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f>>a; f>>b;
    m=strlen(a);
    n=strlen(b);

	for(i=0;i<m;i++)
	{
		ha1=(ha1*10+a[i])%mod1;
		hb1=(hb1*10+b[i])%mod1;
		ha2=(ha2*10+a[i])%mod2;
		hb2=(hb2*10+b[i])%mod2;
		if(i)
		{h1=(h1*10)%mod1;
		h2=(h2*10)%mod2;}
	}

	for(i=0;i<=n-m;i++)
	{
		if(ha1==hb1&&ha2==hb2)
		{
			nr++;
			if(nr<=1000) v[nr]=i;
		}
		hb1=(10*(hb1-(b[i]*h1)%mod1)+b[i+m])%mod1;
		hb2=(10*(hb2-(b[i]*h2)%mod2)+b[i+m])%mod2;
	}
    g<<nr<<'\n';
    for(i=1;i<=nr && i<=1000;i++)
    g<<v[i]<<" ";
}