Cod sursa(job #677679)

Utilizator marius135Dumitran Adrian Marius marius135 Data 10 februarie 2012 14:59:31
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
// Infoarena - Arhiva Educationala Potrivirea Sirurilor 
// Februrie 2012 Marius Dumitran
// Rabin Karp O(n+m)

#include<string.h>
#include<stdio.h>
#define maxn (1<<21)
#define prim1 100007
#define prim2 100021

char sir1[ maxn ], sir2[ maxn ];
int sol[ 2000 ];

int main() {
	
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	
	scanf("%s %s", sir1, sir2);
	int n = strlen(sir1), m = strlen(sir2), nr = 0;
	
	if( n > m )	{
		printf("0\n"); 
		return 0;
	}
	
	int hash1 = 0, hash2 = 0, hash3 = 0 , hash4 = 0, val1 = 1, val2 = 1;
	for (int i = 0; i < n; ++i) {
		
		hash1 = (hash1 * 27 + sir1[i]-'A') % prim1;
		hash2 = (hash2 * 27 + sir1[i]-'A') % prim2;
		hash3 = (hash3 * 27 + sir2[i]-'A') % prim1;
		hash4 = (hash4 * 27 + sir2[i]-'A') % prim2;
		if( i != 0)
			val1 = val1 * 27 % prim1, val2 = val2 * 27 % prim2;
		
	}
	
	if( hash3 == hash1 && hash2 == hash4 ) {
		sol[nr++] = 0;
	}
	for( int i = n; i <= m; ++i ){
		int temp1 = hash3 + prim1 - val1 * (sir2[ i-n] - 'A');
		int temp2 = hash4 + prim2 - val1 * (sir2[ i-n] - 'A');
		hash3 = ((temp1 % prim1) * 27 + sir2[i] - 'A') % prim1;
		hash4 = ((temp2 % prim2) * 27 + sir2[i] - 'A') % prim2;
		if( hash3 == hash1 && hash2 == hash4 ) {
			if( nr > 1000 )
				nr++;
			else 
				sol[nr++] = i - n + 1;
		}
	}
	printf("%d\n", nr);
	for( int i = 0; i < nr && i < 1000; ++i)
		printf("%d ", sol[i]);
	printf("\n");
		
	
	
	
	
	return 0;
}