首页 > 代码库 > ELFHash

ELFHash

HDU1800

 

这题的大意是求出现次数最多的数。所以这题我直接用map做了。

811MS 1876K 差点超时了。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 map<string,int> mp;
 4 
 5 int main(){
 6     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr<<"";
 7     int n;
 8     while(cin>>n){
 9         mp.clear();
10         string str;
11         for(int i = 0; i < n; i ++){
12             cin>>str;
13             int j = 0;
14             for(;j < str.size();j++)if(str[j] != 0) break;
15             mp[str.substr(j)]++;
16         }
17         int ans = 0;
18         for(auto m : mp){
19             ans = max(ans , m.second);
20         }
21         cout<<ans<<endl;
22     }
23     return 0;
24 }

发现网上有一种用ELFHash的做法,就仔细研究了下,由于是位运算,看了好久。

EFLHash模板是:

 1 unsigned int ELFHash(char *str){
 2     unsigned int h = 0;
 3     unsigned int x;
 4     while(*str){
 5         h = (h << 4) + *str++;
 6         x = h & 0xF0000000L;
 7         if(x){
 8             h ^= x>>24;
 9             h &= ~x;
10         }
11     }
12     return h & 0x7FFFFFFF;
13 }

参考了@ACdreamers的文章

 

h = (h << 4) + *str++;   将当前的字符的ASCII的高4位与前一个字符的第4位相加,而低4位存在h中。
x = h & 0xF0000000L;    取出h中最高4位,0xF0000000L代表29~32这4位为1,其余为0。
如果最高4位不为0,则说明字符多与7个,如果不处理的就加入下一个字符的话,第一个字符会被移出去,
新加入的4位为1~4,所以要>>24.(h ^= x>>24;)
h &= ~x;      表示把h的高4位清空。
全部代码为:
608MS 2456K 这个时间比之前用map快了一些了。
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int Mod = 1e5+7;
 4 int Hash[Mod], cnt[Mod];
 5 unsigned int ELFHash(char *str){
 6     unsigned int h = 0;
 7     unsigned int x;
 8     while(*str){
 9         h = (h << 4) + *str++;
10         x = h & 0xF0000000L;
11         if(x){
12             h ^= x>>24;
13             h &= ~x;
14         }
15     }
16     return h & 0x7FFFFFFF;
17 }
18 int Hashhit(char *str){
19     while(*str == 0) str++;
20     int k = ELFHash(str);
21     int t = k % Mod;
22     while(Hash[t] && Hash[t] != k) //有可能发生碰撞,就要清除这个冲突
23         t = (t + 10) % Mod;
24     if(Hash[t] == 0) Hash[t] = k;
25     return ++cnt[t];
26 }
27 int main(){
28     int n;
29     char str[33];
30     while(~scanf("%d",&n)){
31         memset(Hash,0,sizeof(Hash));
32         memset(cnt,0,sizeof(cnt));
33         int ans = 0;
34         for(int i = 0 ; i < n; i ++){
35             scanf("%s",str);
36             ans = max(ans,Hashhit(str));
37         }
38         printf("%d\n",ans);
39     }
40     return 0;
41 }

 

 

 

ELFHash