Cod sursa(job #199693)

Utilizator pitbullpitbulll pitbull Data 20 iulie 2008 10:11:06
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
# include <stdio.h>
# include <string.h>
#define FILE_IN "strmatch.in"
#define FILE_OUT "strmatch.out"
#define MAX 2000000
#define MAXSOL 10

char A[MAX],B[MAX];
int nr=0;
int sol[MAXSOL];

int hash(char* s,int n){
	int sum=0;
	int i;
	for (i=0;i<n;i++)
		sum+=s[i];
	return sum;
}



int main (){
	freopen("strmatch.in", "rt", stdin);  
	scanf("%s %s",A,B);
	
	
	int tmp_hash=hash(B,strlen(A));
	int hash_sub=hash(A,strlen(A));
	int i,dim=strlen(B)-strlen(A);
	int dimA=strlen(A);
	
	
	if(strlen(A)<=strlen(B)){
		for (i=0;i<=dim;i++){
			if(tmp_hash==hash_sub){
				if(!strncmp(B+i,A,dimA)){
					nr++;
					sol[nr-1]=i;
					if(nr==MAXSOL)
						break;
				}
			}
			tmp_hash+=B[i+dimA]-B[i];	
		}
	}
	
	FILE* out=fopen(FILE_OUT,"wt");
	fprintf(out,"%d\n",nr);
	for (i=0;i<nr;i++)
		fprintf(out,"%d ",sol[i]);
	fclose(out);
	
	return 0;
}