• <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)論排行榜

            久久久91精品国产一区二区三区| 久久国产免费直播| 亚洲va久久久噜噜噜久久天堂| 狠狠综合久久综合88亚洲| 久久国产精品无| 99久久国产热无码精品免费| 久久精品亚洲乱码伦伦中文| 伊人久久大香线蕉亚洲| 久久er国产精品免费观看8| 99久久国产宗和精品1上映 | 久久这里有精品视频| 国产A三级久久精品| 久久精品成人| 国产午夜久久影院| 久久精品国产久精国产果冻传媒| 日本久久久久久中文字幕| 午夜久久久久久禁播电影 | 亚洲精品国产综合久久一线| 久久99国内精品自在现线| 久久免费视频一区| 99久久国产综合精品成人影院| 日产精品久久久久久久| 久久这里都是精品| 久久天天躁狠狠躁夜夜2020老熟妇| 国产国产成人精品久久| 亚洲精品白浆高清久久久久久| 亚洲国产成人久久综合野外| 久久国产香蕉视频| 狠狠综合久久综合中文88| 99久久精品费精品国产| 国产精品美女久久久| 久久香蕉超碰97国产精品 | 久久久久久久久66精品片| 久久久久亚洲精品中文字幕| 精品久久久久久久久久久久久久久 | 久久无码AV一区二区三区| 久久性生大片免费观看性| 看全色黄大色大片免费久久久| 色综合合久久天天给综看| 久久亚洲国产精品123区| 亚洲伊人久久综合影院|