基础hash的板子(慢的很

基础hash的板子(慢的很

2019年11月6日 3 作者 Ender

hash用于快速判断字符串是否相同,以洛谷P3370为例讲一下我的思路

#include <iostream>
#include <cstring>
#include <algorithm>

const int N = 1e5 + 233;
std::string a[N];
int n;
int ans[N];
int cnt;
int main() {
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= a[i].size(); j++) {
            ans[i] += (2 << (int)a[i][j]);
        }
    }
    std::sort(ans + 1, ans + n + 1);
    for(int i = 1; i <= n; i++) if(ans[i] != ans[i - 1]) {cnt++;}
    std::cout << cnt;
    return 0;
}

每个a[i]中,2<<a[i][j]+2<<a[i][j+1]+…+2<<a[i][m]来得到hash值,sort排序后贪心判重,统计答案数量,显然这是我瞎搞的写法,没想到居然一遍过,只能说明数据太水了吧。

为了解决hash冲突的问题,其实可以用其他数的次方多重判断,比如用2的a[i][j]次方然后再用7的a[i][j]次方多重判断,这样就可以有效防止hash冲突。

还有一种思路就是使用trie树,显然比我的垃圾算法高效,很久以前发过一篇trie的模板,可以参考一下,修改一下统计答案部分即可。