SHARE
TWEET

Untitled

a guest Apr 25th, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include <stdbool.h>
  5.  
  6. // Uncomment line with "#define DEBUG" if you want to see your hashtable.
  7. // But rememeber to send only solutions with debug turned off!
  8. // #define DEBUG 1
  9. #define MAX_CHARS 30
  10.  
  11. typedef unsigned int uint;
  12.  
  13. typedef struct Node {
  14.     char text[MAX_CHARS];
  15.     struct Node *next;
  16. } Node;
  17.  
  18. uint hashfunc(const char* txt) {
  19.     int p = 2137;
  20.     uint h = 0;
  21.     for (int i = 0; i < strlen(txt); i++)
  22.         h = h*p + txt[i];
  23.     return h;
  24. }
  25.  
  26. void add_to_hashtable(Node** hashtable, int n, const char* txt) {
  27.     Node *node = (Node*)malloc(sizeof(Node));
  28.     strcpy(node->text, txt);
  29.     uint hash = hashfunc(txt) % n;
  30.     node->next = hashtable[hash];
  31.     hashtable[hash] = node;
  32. }
  33.  
  34. bool check_if_exists(Node** hashtable, int n, const char* txt) {
  35.     if (n == 0) return false;
  36.     uint hash = hashfunc(txt) % n;
  37.     Node* ptr;
  38.     ptr = hashtable[hash];
  39.     while (ptr != NULL) {
  40.         if (strcmp(ptr->text, txt) == 0) {
  41.             return true;
  42.         }
  43.         ptr = ptr->next;
  44.     }
  45.     return false;
  46. }
  47.  
  48. void free_memory(Node** hashtable, int n) {
  49.     Node *ptr, *nxt;
  50.     for (int i = 0; i < n; i++) {
  51.         ptr = hashtable[i];
  52.         while (ptr != NULL) {
  53.             nxt = ptr->next;
  54.             free(ptr);
  55.             ptr = nxt;
  56.         }
  57.     }
  58.     free(hashtable);
  59. }
  60.  
  61. void debug_print_hashtable(Node** hashtable, int n) {
  62.     #ifdef DEBUG
  63.         Node* ptr;
  64.         for (int i = 0; i < n; i++) {
  65.             printf("%d: ", i);
  66.             ptr = hashtable[i];
  67.             while (ptr != NULL) {
  68.                 printf("%s | ", ptr->text);
  69.                 ptr = ptr->next;
  70.             }
  71.             printf("\n");
  72.         }
  73.     #endif
  74. }
  75.  
  76. int main() {
  77.     int Z;
  78.     scanf("%d", &Z);
  79.  
  80.     while (Z--) {
  81.         int n, k;
  82.         char tmp[MAX_CHARS];
  83.  
  84.         scanf("%d", &n);
  85.         scanf("%d", &k);
  86.  
  87.         Node** hashtable = (Node**)calloc(n, sizeof(Node*));
  88.  
  89.         for (int i = 0; i < n; i++)
  90.             hashtable[i] = NULL;
  91.  
  92.         for (int i = 0; i < n; i++) {
  93.             scanf("%s", tmp);
  94.             add_to_hashtable(hashtable, n, tmp);
  95.         }
  96.  
  97.         debug_print_hashtable(hashtable, n);
  98.  
  99.         for (int i = 0; i < k; i++) {
  100.             scanf("%s", tmp);
  101.             if (check_if_exists(hashtable, n, tmp)) {
  102.                 printf("YES\n");
  103.             } else {
  104.                 printf("NO\n");
  105.             }
  106.         }
  107.         free_memory(hashtable, n);
  108.     }
  109. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top