人生第一次hash

人生的第一次hash交给了模板题。

讲道理，还没有别人快排要快，就比暴力快那么一点。。。

难道我写的hash就那么菜么？

我想了想，光是处理字符串就O（n*len）。。

这是hash的正确写法吗？我都开始怀疑自己了。

不管怎样，把代码附上，以后可能会用。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>

using namespace std;

int n;
string h[1000007], s;

const int mod = 1000007;

long long hash()
{
    int i, len = s.length() - 1;
    long long ans = 0;
    for(i = 0; i <= len; i++) ans = ans * 33 + s[i] - 'a';
    ans = abs(ans);
    ans %= mod;
    return ans;
}

bool insert()
{
    long long i = hash();
    while(h[i] != s && h[i] != "") i++;
    if(h[i] == s) return 0;
    h[i] = s;
    return 1;
}

int main()
{
    int i, j, ans = 0;
    scanf("%d", &n);
    getline(cin, s);
    for(i = 1; i <= n; i++)
    {
        getline(cin, s);
        if(insert()) ans++;
    }
    printf("%d", ans);
    return 0;
}

View Code

学习了别人的写法，200ms，感觉这才是正确姿势。

原来的我还是太naive了。

 1 #include <cstdio>
 2 #include <cstring>
 3 #define ULL unsigned long long
 4 
 5 const int MAXN = 1000008, p = 1000007;
 6 int n, ans, cnt;
 7 int head[MAXN], next[MAXN];
 8 ULL val[MAXN];
 9 char s[MAXN];
10 
11 inline bool insert(ULL x)
12 {
13     int i, a = x % p;
14     for(i = head[a]; i != -1; i = next[i])
15         if(val[i] == x)
16             return 0;
17     val[cnt] = x;
18     next[cnt] = head[a];
19     head[a] = cnt++;
20     return 1;
21 }
22 
23 inline void ha()
24 {
25     int i, len = strlen(s);
26     ULL hash = 0;
27     for(i = 0; i < len; i++) hash = hash * 17 + s[i];
28     ans += insert(hash);
29 }
30 
31 int main()
32 {
33     int i;
34     memset(head, -1, sizeof(head));
35     scanf("%d", &n);
36     while(n--)
37     {
38         scanf("%s", s);
39         ha();
40     }
41     printf("%d", ans);
42     return 0;
43 }

View Code