Cod sursa(job #702022)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 1 martie 2012 19:03:53
Problema Potrivirea sirurilor Scor 28
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <cstring>
#define MOD1 666013
#define MOD2 999073
#define B 73
using namespace std;
int s,ha1,ha2,hb1,hb2,put1,put2,i,n,m,sol[1001];
string a,b;
int main()
{
	ifstream fi("strmatch.in");
	ofstream fo("strmatch.out");
	getline(fi,a);
	getline(fi,b);
	m=a.size(); n=b.size();
	put1=put2=1;
	for(i=0;i<m;i++)
	{
		ha1=(B*ha1+a[i])%MOD1;
		ha2=(B*ha2+a[i])%MOD2;
		hb1=(B*hb1+b[i])%MOD1;
		hb2=(B*hb2+b[i])%MOD2;
		if(i) { put1=(put1*B)%MOD1; put2=(put2*B)%MOD2; }
	}
	if(ha1==hb1 and ha2==hb2) sol[++s]=0;
	for(i=1;i<n-m+1;i++)
	{
		hb1=((hb1-(put1*b[i-1])%MOD1+MOD1)*B+b[i+m-1])%MOD1;
		hb2=((hb2-(put2*b[i-1])%MOD2+MOD2)*B+b[i+m-1])%MOD2;
		if(ha1==hb1 and ha2==hb2 and i<1000)   sol[++s]=i; else if(ha1==hb1 and ha2==hb2) s++;
	}
	fo<<s<<"\n";
	for(i=1;i<=s;i++) fo<<sol[i]<<" ";
	fo<<"\n";
}