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日 3670点热度 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++ STL中队列(queue)及优先队列(priority_queue)笔记 StickerMule Unix贴纸特价仅1刀包邮全球 React 配合后端热更新 从台湾网路书店爬取图书信息小记 Jawbone Jambox Mini蓝牙音响上车指南与刷机 情色漫画老师OVA两话2160P
标签聚合
动漫 日常 C++ 洛谷 C/C++ OI HTML ST
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

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

Theme Kratos Made By Seaton Jiang