• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            A Za, A Za, Fighting...

            堅(jiān)信:勤能補(bǔ)拙

            PKU 2503 Babelfish

            問(wèn)題:
            http://acm.pku.edu.cn/JudgeOnline/problem?id=2503

            思路:
            字符串哈希
            這里使用的哈希函數(shù)是ELFHash
             1 int ELFHash(char *str)
             2 {
             3     unsigned long t, hash = 0;
             4     while(*str) {
             5         hash = (hash<<4+ (*str++);
             6         if((t = hash&0xF0000000L))
             7             hash ^= t>>24;
             8         hash &= ~t;
             9     }
            10     return (hash & 0x7FFFFFFF)%PRIME;
            11 }

            因?yàn)橹皩?xiě)哈希表解決沖突都是用的鏈接法,這里想嘗試一下開(kāi)放地址法,采用最簡(jiǎn)單的線性探查,結(jié)果居然TLE
            無(wú)奈還是改成鏈接法,然后就AC了
            不過(guò),時(shí)間卻有719MS之多,而網(wǎng)上幾乎相同的代碼只需要230MS左右,不知道是何原因

            代碼:
            TLE的開(kāi)放地址法
             1 void
             2 insert(int hash_val, int index)
             3 {
             4     if(!hash[hash_val].used) {
             5         hash[hash_val].used = 1;
             6         hash[hash_val].index = index;
             7     } else
             8         insert((hash_val+1)%PRIME, index); /* linear probing */
             9 }
            10 
            11 int
            12 search(char *f_word)
            13 {
            14     int hash_val = ELFHash(f_word);
            15     int i = 0;
            16     while(1) {
            17         if(!hash[hash_val].used || i==PRIME)
            18             break;
            19         if(strcmp(f_word, flg[hash[hash_val].index])==0)
            20             return hash[hash_val].index;
            21         hash_val = (hash_val+1)%PRIME;
            22         ++i;
            23     }
            24     return -1;
            25 }
            26 
            27 void
            28 input_hash()
            29 {
            30     int hash_val, index = 0;
            31     char tmp[MAX_LEN*2+1];
            32     memset(hash, 0sizeof(hash));
            33     while(gets(tmp) && tmp[0]) {
            34         sscanf(tmp, "%s %s", eng[index], flg[index]);
            35         hash_val = ELFHash(flg[index]);
            36         insert(hash_val, index);
            37         ++index;
            38     }
            39 }

            AC的鏈接法
             1 void
             2 insert(int hash_val, int index)
             3 {
             4     struct Node *node = (struct Node *)malloc(sizeof(struct Node));
             5     if(node == NULL) {
             6         fprintf(stderr, "malloc error in: insert\n");
             7         exit(1);
             8     }
             9     node->index = index;
            10     node->next = hash[hash_val];
            11     hash[hash_val] = node;
            12 }
            13 
            14 int
            15 search(char *f_word)
            16 {
            17     int hash_val = ELFHash(f_word);
            18     struct Node *node = hash[hash_val];
            19     while(node != NULL) {
            20         if(strcmp(f_word, flg[node->index]) == 0)
            21             return node->index;
            22         node = node->next;
            23     }
            24     return -1;
            25 }
            26 
            27 void
            28 input_hash()
            29 {
            30     int hash_val, index = 0;
            31     char tmp[MAX_LEN*2+1];
            32     memset(hash, 0sizeof(hash));
            33     while(gets(tmp) && tmp[0]) {
            34         sscanf(tmp, "%s %s", eng[index], flg[index]);
            35         hash_val = ELFHash(flg[index]);
            36         insert(hash_val, index);
            37         ++index;
            38     }
            39 }

            posted on 2010-07-28 11:11 simplyzhao 閱讀(224) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): G_其他

            導(dǎo)航

            <2011年5月>
            24252627282930
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            統(tǒng)計(jì)

            常用鏈接

            留言簿(1)

            隨筆分類(lèi)

            隨筆檔案

            搜索

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            久久r热这里有精品视频| 亚洲一本综合久久| 一级女性全黄久久生活片免费| 女同久久| 亚洲国产一成人久久精品| 九九久久自然熟的香蕉图片| 久久成人18免费网站| 久久亚洲私人国产精品vA| 精品久久久久久国产免费了| 久久精品视频一| 国产精品欧美久久久久天天影视 | 香蕉久久影院| 国产亚洲色婷婷久久99精品| 伊人久久综合热线大杳蕉下载| 欧美成人免费观看久久| 国产69精品久久久久99尤物 | 久久夜色精品国产欧美乱| 久久精品国产清自在天天线| 久久99国产综合精品| 亚洲人AV永久一区二区三区久久| 久久精品国产亚洲AV香蕉| 香蕉久久久久久狠狠色| 国产精品热久久无码av| 久久噜噜电影你懂的| 精品久久久久久久久午夜福利| 亚洲国产精品狼友中文久久久| 国产精品青草久久久久福利99| 99久久成人国产精品免费| 久久精品夜夜夜夜夜久久| 国产aⅴ激情无码久久| 日本高清无卡码一区二区久久| 国产亚洲美女精品久久久| 久久99国产精一区二区三区| 久久99精品久久久久子伦| 日韩精品久久无码中文字幕| 久久精品国产亚洲AV久| 久久综合鬼色88久久精品综合自在自线噜噜 | 亚洲欧美成人久久综合中文网| 久久久噜噜噜久久中文字幕色伊伊| 99精品久久久久久久婷婷| 中文字幕亚洲综合久久|