Cod sursa(job #199667)

Utilizator pitbullpitbulll pitbull Data 20 iulie 2008 00:51:43
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 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);
	
	
	if(strlen(A)<=strlen(B)){
		for (i=0;i<=dim;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;
}