Cod sursa(job #820410)

Utilizator krissu93FMI Tiugan Cristiana Elena krissu93 Data 20 noiembrie 2012 20:00:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

#define mod1 666013
#define mod2 2000003

ifstream in("strmatch.in");
ofstream out("strmatch.out");

char a[2000002],b[2000002];
int  v[2000002];
int nr=0;//numarul de regasiri;

int main()
{	int coda=0,codb=0,coda1=0,codb1=0;
	int i,lb,la;
	int p1=1,p2=1;
	in>>a;
	la=strlen(a);//lungimea lui a;
	in>>b;
	lb=strlen(b);//lungimea lui b;
if (lb<la) out<<"0";
else
{
	for (i=0;i<la;i++)
	{
		coda  = (coda*73 +a[i]) %mod1;
		coda1 = (coda1*73+a[i]) %mod2;
		codb  = (codb*73 +b[i]) %mod1;
		codb1 = (codb1*73+b[i]) %mod2;
		if (i!=0)
		{
			p1=(p1*73)%mod1;
			p2=(p2*73)%mod2;
		}
	}
	if ((coda==codb) && (coda1==codb1))
	{
		v[++nr]=0;
	}
	for (i=la; i<lb; i++)
	{
		codb = (( codb -( b[i-la]*p1 ) %mod1 +mod1 )*73 + b[i] ) % mod1 ;
		codb1= ((codb1 -( b[i-la]*p2 ) %mod2 +mod2 )*73 + b[i] ) % mod2 ;
		if ( (coda==codb) && (coda1==codb1) )
		{
			v[++nr]=i-la+1;
		}
	}
	out<<nr<<"\n";
	for (i=1;i<=nr && i<=1000;i++)
		out<<v[i]<<" ";
}
return 0;
}