We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#include<math.h>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<assert.h>#include<limits.h>#include<stdbool.h>#define MAX_ITEMS 30000typedefstructItem{char*key;intquantity;}Item;intgenerateHash(char*key);Item*search(char*key,Item**hashArray){intindex=generateHash(key);if(strcmp(hashArray[index]->key,key)==0){returnhashArray[index];}else{// Move in the array until you find the itemintlooped=0;while(strcmp(hashArray[index]->key,key)!=0){++index;// If we haven't looped wrap aroundif(!looped){if(index==MAX_ITEMS){index%=MAX_ITEMS;looped=1;}}// If we have loopedelse{// And we reach the last elementif(index==MAX_ITEMS-1)break;}}if(strcmp(hashArray[index]->key,key)==0)returnhashArray[index];elsereturnNULL;}}intgenerateHash(char*key){unsignedlonghash=5381;intc;while((c=*(key++)))hash=((hash<<5)+hash)+c;/* hash * 33 + c */// After this line, the hash has become an indexintnew_hash=(int)(hash%MAX_ITEMS);returnnew_hash;}voidinsert(char*key,Item**hashArray){Item*item=malloc(sizeof(Item));assert(item!=NULL);item->key=malloc(sizeof(char)*6);strcpy(item->key,key);item->quantity=1;intindex=generateHash(key);// If the word has already been inserted into the arrayif(strcmp(hashArray[index]->key,key)==0){hashArray[index]->quantity+=1;}else{// Move in the array until you find an empty/deleted cell or the previous itemwhile(hashArray[index]->key[0]!=-1&&strcmp(hashArray[index]->key,key)!=0){++index;// Wrap aroundindex%=MAX_ITEMS;}if(strcmp(hashArray[index]->key,key)==0)hashArray[index]->quantity+=1;elsehashArray[index]=item;}}Item**newHashArray(){Item*dummyItem=NULL;dummyItem=malloc(sizeof(Item));assert(dummyItem!=NULL);dummyItem->key=malloc(sizeof(char)*6);assert(dummyItem->key!=NULL);memset(dummyItem->key,0,sizeof(char)*6);dummyItem->key[0]=255;dummyItem->quantity=-1;Item**hashArray=malloc(sizeof(Item*)*MAX_ITEMS);assert(hashArray!=NULL);for(inti=0;i<MAX_ITEMS;i++){hashArray[i]=dummyItem;}returnhashArray;}intmain(){intm;intn;scanf("%d %d",&m,&n);Item**hashArray=newHashArray();char**magazine=malloc(sizeof(char*)*m);for(intmagazine_i=0;magazine_i<m;magazine_i++){magazine[magazine_i]=(char*)malloc(10240*sizeof(char));scanf("%s",magazine[magazine_i]);insert(magazine[magazine_i],hashArray);}char**ransom=malloc(sizeof(char*)*n);for(intransom_i=0;ransom_i<n;ransom_i++){ransom[ransom_i]=(char*)malloc(10240*sizeof(char));scanf("%s",ransom[ransom_i]);Item*found_item=search(ransom[ransom_i],hashArray);if(found_item==NULL){printf("No\n");return0;}elsefound_item->quantity-=1;if(found_item->quantity<0){printf("No\n");return0;}}printf("Yes");return0;}
Hash Tables: Ransom Note
You are viewing a single comment's thread. Return to all comments →
I'm also getting a segmentation fault in C. It's for test cases 16 & 17, but my code works when I compile using gcc -g -Wall on my local machine.
gcc 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.4)
I'm using Windows Subshell for Linux.