Cod sursa(job #1358130)

Utilizator PetrutiuPaulPetrutiu Paul Gabriel PetrutiuPaul Data 24 februarie 2015 13:19:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int P=69;

const long long MOD1=100007;
const long long MOD2=100021;

int hash1,hash2,hashA1,hashA2,NA,NB,Nr;

char A[2000005],B[2000005];
bool match[2000005];


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