Cod sursa(job #1168219)

Utilizator federerUAIC-Padurariu-Cristian federer Data 7 aprilie 2014 15:21:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include<fstream>
#include<cstring>
#define Nmax 2000010
using namespace std;

#define P 73
#define MOD1 100007
#define MOD2 100021

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

char A[Nmax], B[Nmax];
int i, P1=1, P2=1;
int matches[Nmax], NrM;
int main()
{
	fin>>A>>B;
	int NA=strlen(A);
	int NB=strlen(B);
	if(NA>NB)
	{
		fout<<0<<'\n';
		return 0;
	}
	int hashA1=0, hashA2=0;
	for(i=0;i<NA;++i)
	{
		hashA1=(hashA1*P+A[i])%MOD1;
		hashA2=(hashA2*P+A[i])%MOD2;
		if(i>0)
			P1=(P1*P)%MOD1,
			P2=(P2*P)%MOD2;
	}
	int hash1=0, hash2=0;
	for(i=0;i<NA;++i)
	{
		hash1=(hash1*P+B[i])%MOD1;
		hash2=(hash2*P+B[i])%MOD2;
	}
	if(hash1==hashA1 && hash2==hashA2)
		matches[0]=1,
		NrM=1;
	for(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)
			matches[i-NA+1]=1,
			NrM++;
	}
	fout<<NrM<<'\n';
	NrM=0;
	for(i=0;i<NB&&NrM<1000;++i)
		if(matches[i])
			fout<<i<<' ';
	fout<<'\n';
	return 0;
}