Skip to content

Instantly share code, notes, and snippets.

@bojieli
Last active August 29, 2015 14:17
Show Gist options
  • Save bojieli/0d2d41e4c7c55aee775d to your computer and use it in GitHub Desktop.
Save bojieli/0d2d41e4c7c55aee775d to your computer and use it in GitHub Desktop.
词典
#include<stdio.h>
#include<stdlib.h>
#define HASH_SIZE 300007
#define LINE_LEN 32
char dict[HASH_SIZE][LINE_LEN] = {0};
static unsigned int BKDRhash(char* key) {
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;
while (*key)
{
hash = hash * seed + (*key++);
}
return hash;
}
static void add_hash(char* l) {
int hash = BKDRhash(l) % HASH_SIZE;
while (dict[hash][0] != 0) {
hash++;
if (hash == HASH_SIZE)
hash = 0;
}
memcpy(dict[hash], l, LINE_LEN);
}
static char* find_hash(char* l) {
int hash = BKDRhash(l) % HASH_SIZE;
while (dict[hash][0]) {
if (strcmp(l, dict[hash]) == 0)
return dict[hash];
++hash;
if (hash == HASH_SIZE)
hash = 0;
}
return NULL;
}
int main() {
char s[LINE_LEN] = {0}, l[LINE_LEN] = {0};
while (gets(s)) {
char *space;
if (strlen(s) == 0)
break;
space = strchr(s, ' ');
if (!space)
break;
memset(l, 0, LINE_LEN);
// reverse <native, foreign> to <foreign, native>
strcpy(l, space+1);
memcpy(l + strlen(l) + 1, s, space-s);
add_hash(l);
}
while (scanf("%s", l) != EOF) {
char *d = find_hash(l);
if (d) {
d += strlen(d) + 1; // move beyond separator \0
printf("%s\n", d);
}
else {
printf("eh\n");
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment