Cod sursa(job #199666)

Utilizator pitbullpitbulll pitbull Data 20 iulie 2008 00:47:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
# include <stdio.h>
# include <string.h>
#define FILE_IN "strmatch.in"
#define FILE_OUT "strmatch.out"
#define MAX 1<<21
#define MAXSOL 1000

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 compare(char* s1,char* s2){//s2 e substringul;s1 e o bucata din stringul mare
	int i;
	for (i=0;i<strlen(s2);i++)
			if(s1[i]!=s2[i])
				return 1;
	return 0;
}

int main (){
	FILE* in=fopen(FILE_IN,"rt");
	fscanf(in,"%s",A);//sirul de cautat
	fscanf(in,"%s",B);//sirul in care se cauta
	fclose(in);
	
	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);
	
	
	for (i=0;i<=dim+1;i++){
		if(tmp_hash==hash_sub){
			if(!compare(B+i,A)){
				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;
}