词典

3.c

#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");
        }
    }
}