Cod sursa(job #629405)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 3 noiembrie 2011 12:02:22
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <stdio.h>
#include <string.h>

#define p 73
#define max_n 2000001
#define mod1 100021
#define mod2 100007

using namespace std;

char a[max_n],b[max_n];
int na,nb,match[max_n],i,hashA1,hashA2,hashB1,hashB2,p1,p2;
int sol[max_n],nr;

int main () {
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	gets(a);
	gets(b);
	na=strlen(a);
	nb=strlen(b);

	if (na>nb) {
		printf("0\n");
		return 0;
	}

	hashA1=hashA2=hashB1=hashB2=0;
	p1=p2=1;
	nr=0;
	for (i=0; i<na; i++){
		hashA1=(hashA1*p+a[i])%mod1;
		hashA2=(hashA2*p+a[i])%mod2;
		if (i) {
			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) {
		sol[0]=1;
		nr++;
	}

	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)
			sol[i-na+1]=1;
	}

	nr=0;
	for (i=0; i<nb; i++)
		if (sol[i]==1) nr++;
	printf("%d\n",nr);
	if (nr>1000) nr=1000;
	int x=0;
	for (i=1; i<=nb && x<=nr; i++)
		if (sol[i]) {
		printf("%d ",i);
		x++;
		}
	return 0;
}