首页 > 代码库 > 人生第一次hash

人生第一次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

 

人生第一次hash