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日 2625点热度 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
取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版
祝大家9102年新年快乐! HDU 1806 Frequent values(区间RMQ问题)题解 #动画#《多田君不恋爱》观后感:内心永远是彩虹色! 家中组无线网络全覆盖 教你如何观看性感荷官在线发牌 人的一生都在治愈自己的童年
标签聚合
HTML 日常 OI C/C++ C++ ST 动漫 洛谷
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

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

Theme Kratos Made By Seaton Jiang