C/C++字符串哈希（单哈希）Hash算法模板

2018年8月2日 2767点热度 6人点赞 0条评论

简介

Hash算法类似于给字符串进行加密的方式，方便判断重复

那字符串Hash就非常好理解了。就是把字符串转换成一个整数的函数。而且要尽量做到使字符串对应唯一的Hash值。

进制哈希是最常见（NOIP）的哈希方式

它的主要思路是选取恰当的进制，可以把字符串中的字符看成一个大数字中的每一位数字，不过比较字符串和比较大数字的复杂度并没有什么区别(高精数的比较也是 $O (n)$

评测：洛谷P3370

模板

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

typedef unsigned long long LL;

const int MAXN = 10015;
const int Base = 131;
const int Prime = 19260817;
const LL MOD = 212370440130137957;


int n;
int ans = 1;

char s[MAXN];
LL a[MAXN];

LL hash(char* );

int main() {
	cin >> n;
	for(int i = 1;i <= n;++i) {
		scanf("%s",s);
		a[i] = hash(s);
	}
	sort(a + 1,a + n + 1);
	for(int i = 1;i < n;++i)
		if(a[i] != a[i + 1]) ans++;
	printf("%d\n",ans);
	return 0;
}
LL hash(char s[]) {
	int len = strlen(s);
	LL cnt = 0;
	for(int i = 0;i < len;++i)
		cnt = (cnt * Base + (LL)s[i]) % MOD + Prime;
	return cnt;
}