Cod sursa(job #562016)

Utilizator SadmannCornigeanu Calin Sadmann Data 22 martie 2011 09:45:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<fstream>
#include<cstring>
#define NMAX 2000001
#define P 73
#define MOD1 100007
#define MOD2 100021
using namespace std;

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

char A[NMAX],B[NMAX];
int NA,NB,hashA1,hashA2,P1=1,P2=1,hash1,hash2;
char match[NMAX];

int main()
{
	in>>A>>B;
	if( (NA=strlen(A)) > (NB=strlen(B)) )
	{
		out<<"0\n";
		return 0;
	}
	
	for(int i=0;i<NA;i++)
	{
		hashA1=(hashA1*P+A[i])%MOD1;
		hashA2=(hashA2 * P + A[i]) % MOD2;
		
		hash1=(hash1*P+B[i])%MOD1;
		hash2=(hash2*P+B[i])%MOD2;
		
		if(i)
		{
			P1=(P1*P)%MOD1;
			P2=(P2*P)%MOD2;
		}
	}
	
	int NR=0;
	if(hash1==hashA1 && hash2==hashA2)
		match[0]=++NR; //=1 , nr++ dar e mai eficient asa
	for(int i=NA;i<NB;i++)
	{
		hash1 = ((hash1 - (B[i - NA] * P1) % MOD1 + MOD1) * P + B[i]) % MOD1;
		hash2 = ((hash2 - (B[i - NA] * P2) % MOD2 + MOD2) * P + B[i]) % MOD2;
		if(hash1==hashA1 && hash2==hashA2)
			match[i-NA+1]=1,NR++;
	}
	out<<NR<<"\n";
	
		for(int i=NR=0;i<NB && NR<1000;i++)
			if(match[i])
			{
				out<<i<<" ";
				NR++;
			}
	out<<"\n";
			
	return 0;
}