Cod sursa(job #509514)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 11 decembrie 2010 11:25:38
Problema Potrivirea sirurilor Scor 72
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <stdio.h>
#define MOD1 1000007
#define MOD2 1000021
#define SIGMA 27
#define NMAX 2000010
char S[NMAX];
int v[1024];
int n, m;
inline void mod(int &x, int MOD){
	while( x < 0) x += MOD;
	while( x >= MOD) x -= MOD;
}
int main(){
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	int hash1 = 0, hash2 = 0, put1 = 1, put2 = 1;
	fgets(S, NMAX, stdin);
	int lung = 0;
	for(int i = 0; S[i] != '\n' && S[i]; ++i){
		hash1 = (hash1 * SIGMA + S[i] - 'A' + 1) % MOD1;
		hash2 = (hash2 * SIGMA + S[i] - 'A' + 1) % MOD2;
		if(i != 0) {
			put1 = (put1 * SIGMA) % MOD1;
			put2 = (put2 * SIGMA) % MOD2;
		}
		lung = i;
	}
	fgets(S, NMAX, stdin);
	int h1 = 0, h2 = 0;
	for(int i = 0; i <= lung && S[i] && S[i] != '\n'; ++i){
		h1 = (h1 * SIGMA + S[i] - 'A' + 1) % MOD1;
		h2 = (h2 * SIGMA + S[i] - 'A' + 1) % MOD2;
	}
	if(h1 == hash1 && hash2 == h2) v[++v[0]] = 0;
	for(int i = lung + 1; S[i] && S[i] != '\n' ; ++i){
		h1 = ((h1 - ((S[i-lung-1]-'A'+1) * put1) % MOD1 + MOD1) * SIGMA + S[i] - 'A' + 1)%MOD1;
		h2 = ((h2 - ((S[i-lung-1]-'A'+1) * put2) % MOD2 + MOD2) * SIGMA + S[i] - 'A' + 1)%MOD2;
		mod(h1, MOD1);
		mod(h2, MOD2);
		if(h1 == hash1 && h2 == hash2){
			v[0]++;
			if(v[0] <= 1000) v[v[0]] = i-lung;
		}
	}
	printf("%d\n", v[0]);
	for(int i = 1; i <= 1000 && i <= v[0]; ++i)
		printf("%d ", v[i]);
	printf("\n");
	return 0;
}