APTX Blog

A Moe Blog Set Up By APTX

C/C++字符串哈希(单哈希)Hash算法 模板

文章目录[隐藏]

简介

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;
}

参考链接:https://www.cnblogs.com/Slager-Z/p/7807011.html

https://www.luogu.org/problemnew/solution/P3370

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注