Cod sursa(job #629419)

Utilizator irene_mFMI Irina Iancu irene_m Data 3 noiembrie 2011 12:10:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <cstdio>
#include <cstring>
#define MaxN 2000005
#define MaxS 1002

const int P = 73, MOD1 = 1000007, MOD2 = 666013;
char A[ MaxN ], B[ MaxN ];
int NA, NB, hashA1, hashA2, hashB1, hashB2, i, P1 = 1, P2 = 1, poz[ MaxS ], nrSol;

int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	
	scanf("%s %s", &A, &B);
	NA = strlen( A ); NB = strlen( B );
	if( NA > NB )
	{
		printf("0\n");
		return 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;
		}
	}
	
	for( i = 0; i < NA ; ++i )
	{
		hashB1 = ( hashB1 * P + B[ i ] ) % MOD1;
		hashB2 = ( hashB2 * P + B [ i ] ) % MOD2;
	}
	
	if( hashA1 == hashB1 && hashA2 == hashB2 )
		poz [ ++ nrSol ] = 0;
	
	for( i = NA ; i < NB ; ++i )
	{
		hashB1 = ( ( hashB1 - ( B[ i - NA ] * P1 ) % MOD1 + MOD1 ) * P + B[ i ] ) % MOD1;
		hashB2 = ( ( hashB2 - ( B[ i - NA ] * P2 ) % MOD2 + MOD2 ) * P + B[ i ] ) % MOD2;
		
		if( hashA1 == hashB1 && hashA2 == hashB2)
		{
			nrSol ++;
			if( nrSol < 1000 )
				poz[ nrSol ] = i - NA +1 ;
		}
	}
	
	printf("%d\n", nrSol);
	if( nrSol <= 1000 )
		for( i = 1; i <= nrSol ; ++i)
			printf( "%d ", poz[ i ] );
	else
		for( i = 1; i <= 1000 ; ++i)
			printf( "%d ", poz[ i ] );
		
	return 0;
}