fork download
copy 
  1. #include<stdio.h>
  2. #include<string.h>
  3.  
  4. #define M 4000000
  5. #define NIL (-1)
  6. #define L 14
  7.  
  8. char H[M][L]; /* Hash Table */
  9.  
  10. int getChar(char ch){
  11.   if ( ch == 'A') return 1;
  12.   else if ( ch == 'C') return 2;
  13.   else if ( ch == 'G') return 3;
  14.   else if ( ch == 'T') return 4;
  15. }
  16.  
  17. /* convert a string into an integer value */
  18. long long getKey(char str[]){
  19.   long long sum = 0, p = 1, i;
  20.   for ( i = 0; i < strlen(str); i++ ){
  21.     sum += p*(getChar(str[i]));
  22.     p *= 5;
  23.   }
  24.   return sum;
  25. }
  26.  
  27. int h1(int key){ return 0x7fffFFFF & ((key << 16) | (key >> 16)); }
  28. int h2(int key){ return 0x7fffFFFF ^ key; }
  29.  
  30. int find(char str[]){
  31.  
  32.     /* your task */
  33.     long long key = getKey(str);
  34.     int h;
  35.     h = (int)(0x7fffFFFFLL & (key >> 32)) % M;
  36.     if (strcmp(H[h], str) == 0) return 1;
  37.     h = (int)(0x7fffFFFFLL & key) % M;
  38.     if (strcmp(H[h], str) == 0) return 1;
  39.     h = h1((int)(0x7fffFFFFLL & (key >> 32))) % M;
  40.     if (strcmp(H[h], str) == 0) return 1;
  41.     h = h2((int)(0x7fffFFFFLL & (key >> 32))) % M;
  42.     if (strcmp(H[h], str) == 0) return 1;
  43.     h = h1((int)(0x7fffFFFFLL & key)) % M;
  44.     if (strcmp(H[h], str) == 0) return 1;
  45.     h = h2((int)(0x7fffFFFFLL & key)) % M;
  46.  
  47.     while (H[h][0] != '\0') {
  48.     	if (strcmp(H[h], str) == 0) {
  49.     		return 1;
  50.     	}
  51.     	++h;
  52.     	if (h == M) {
  53.     		h = 0;
  54.     	}
  55.     }
  56. 	return 0;
  57. }
  58.  
  59. int insert(char str[]){
  60.  
  61.     /* your task */
  62.     long long key = getKey(str);
  63.     int h;
  64.     h = (int)(0x7fffFFFFLL & (key >> 32)) % M;
  65.     if (H[h][0] == '\0') {
  66.     	strcpy(H[h], str);
  67.     	return h;
  68.     }
  69.     h = (int)(0x7fffFFFFLL & key) % M;
  70.     if (H[h][0] == '\0') {
  71.     	strcpy(H[h], str);
  72.     	return h;
  73.     }
  74.     h = h1((int)(0x7fffFFFFLL & (key >> 32))) % M;
  75.     if (H[h][0] == '\0') {
  76.     	strcpy(H[h], str);
  77.     	return h;
  78.     }
  79.     h = h2((int)(0x7fffFFFFLL & (key >> 32))) % M;
  80.     if (H[h][0] == '\0') {
  81.     	strcpy(H[h], str);
  82.     	return h;
  83.     }
  84.     h = h1((int)(0x7fffFFFFLL & key)) % M;
  85.     if (H[h][0] == '\0') {
  86.     	strcpy(H[h], str);
  87.     	return h;
  88.     }
  89.     h = h2((int)(0x7fffFFFFLL & key)) % M;
  90.  
  91. 	while (H[h][0] != '\0') {
  92.     	++h;
  93.     	if (h == M) {
  94.     		h = 0;
  95.     	}
  96.     }
  97. 	strcpy(H[h], str);
  98. 	return h;
  99. }
  100.  
  101. int main(){
  102.     int i, n, h;
  103.     char str[L], com[9];
  104.     for ( i = 0; i < M; i++ ) H[i][0] = '\0';
  105.  
  106.     scanf("%d", &n);
  107.  
  108.     for ( i = 0; i < n; i++ ){
  109. 		scanf("%s %s", com, str);
  110.  
  111. 		if ( com[0] == 'i' ){
  112. 		    insert(str);
  113. 		} else {
  114. 		    if (find(str)){
  115. 				printf("yes\n");
  116. 		    } else {
  117. 				printf("no\n");
  118. 		    }
  119. 		}
  120.     }
  121.  
  122.     return 0;
  123. }
  124.  
Success #stdin #stdout 0.04s 56984KB
comments (?)
stdin
copy 
13
insert AAA
insert AAC
insert AGA
insert AGG
insert TTT
find AAA
find CCC
find CCC
insert CCC
find CCC
insert T
find TTT
find T
stdout
copy 
yes
no
no
yes
yes
yes
https://ideone.com/2Ong7J
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!