题目链接

• 简单的字符串HASH题目，关键学习一下黑书的字符串elfhash

const int MAXN = 100010;

const int maxn=1000000;
const int maxm=100003;
const int maxlen=20;

class hash
{
    private:
    struct node{
        char ch[maxlen];
        int ptr;
        node* next;
    };
    node *h[maxm],s[maxn];
    int numptr;
    int Hash(char *key)
    {
        unsigned long h=0,g;
        while(*key)
        {
            h=(h<<4)+*key++;
            g=h&0xf0000000L;
            if(g)h^=g>>24;
            h&=~g;
        }
        return h%maxm;
    }
    public:
    void init()
    {
        int i;
        for(i=0;i<maxm;i++)h[i]=NULL;
        numptr=0;
    }
    int ins(char ch[])
    {
        int temp=Hash(ch);
        strcpy(s[numptr].ch,ch);
        s[numptr].next=h[temp];
        s[numptr].ptr=numptr;
        h[temp]=&s[numptr];
        numptr++;
        return numptr-1;
    }
    int question(char ch[])
    {
        int temp=Hash(ch);
        node* ptr=h[temp];
        while(ptr)
        {
            if(strcmp(ptr->ch,ch)==0)
            {
                return ptr->ptr;
            }
            ptr=ptr->next;
        }
        return -1;
    }
} hash;

char ipt[30], a[20], b[20];
char ans[MAXN][20];

int main ()
{
    hash.init();
    while (gets(ipt) && ipt[0] != 0)
    {
        sscanf(ipt, "%s %s", a, b);
        int hs = hash.ins(b);
        strcpy(ans[hs], a);
    }
    while (gets(ipt) && ipt[0] != 0)
    {
        int hs = hash.question(ipt);
        if (hs != -1)
            printf("%s\n", ans[hs]);
        else
            puts("eh");
    }
    return 0;
}
/*
dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

atcay
ittenkay
oopslay
Sample Output

cat
eh
loops
*/