Advertisement
Guest User

Untitled

a guest
Apr 25th, 2019
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.14 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement