APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By ミズキ
  1. 首页
  2. OI
  3. 正文

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

2018年8月2日 3636点热度 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;
}

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

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

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: C/C++ C++ Hash 哈希 字符串 模板 洛谷 算法 落谷
最后更新:2018年8月3日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
上岸 Star Divine 现代前端工程师发展方向不完全指北 站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话
#洛谷#C/C++P4470 [BJWC2018]售票 教你如何观看性感荷官在线发牌 我没有经验,还真是抱歉呢 C++快读快写模板 二次元头像(老婆)生成器 Google空间(XSpace)自动配置谷歌框架/直连谷歌商店
标签聚合
HTML 日常 洛谷 OI ST 动漫 C++ C/C++
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang