Cod sursa(job #616738)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 13 octombrie 2011 11:13:58
Problema Potrivirea sirurilor Scor 26
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[1001],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;
}