赞
踩
视频链接:F02 字符串哈希 bilibili
把字符串映射成一个 p p p 进制数字,对于一个长度为 n n n 的字符串 s s s
如果两个字符串不一样但 H a s h Hash Hash 函数值一样,这样的现象被称作哈希碰撞
解决哈希碰撞的方法(极大程度减少哈希碰撞次数,但还是有可能碰撞)
const int N=1e5+5; // 最大字符串的个数
const int M=1.5e3+10; // 题目中字符串的最大长度
const int P=131; // 131,13331不容易哈希碰撞
// p[i]:表示p的i次方
// h[i]:表示s[1~i]的哈希值,如h[2]表示字符串s前两个字符组成字符串的哈希值
ULL p[N],h[N];
char s[M]; // 存储字符串
int n;
// 预处理hash函数的前缀和,时间复杂度O(n)
void init() {
// p^0=1,空串哈希值为0
p[0]=1,h[0]=0;
for(int i=1;i<=n;i++) {
p[i]=p[i-1]*P;
h[i]=h[i-1]*P+s[i]; // 前缀和计算公式
}
}
// 计算s[l~r](子串)的hash值,时间复杂度O(1)
ULL get(int l,int r) {
return h[r]-h[l-1]*p[r-l+1]; // 区间和计算字串的hash值
}
// 判断两个子串是否相同
bool substr(int l1,int r1,int l2,int r2) {
return get(l1,r1)==get(l2,r2);
}
题目链接:P3370 【模板】字符串哈希 - 洛谷
#include<bits/stdc++.h> #define x first #define y second using namespace std; typedef long long ll; typedef unsigned long long ULL; typedef pair<int,int> PII; // 解题思路: const int N=1e5+5; // 字符串数量上界 const int M=1.5e3+10; // 单个字符串最大长度 const int P=131; // 131,13331不容易哈希碰撞 // h[i]:表示s[1~i]的哈希值,如h[2]表示字符串s前两个字符组成字符串的哈希值 ULL h[N]; char str[M]; // 存储字符串 set<ULL> s; // 存储每个字符串的哈希值,集合自动去重 int n; // 计算字符串s的哈希值 ULL Hash(char str[]) { h[0]=0; // 空串哈希值为0 int len=strlen(str+1); // 计算长度 for(int i=1;i<=len;i++) { h[i]=h[i-1]*P+str[i]; } return h[len]; // 返回此串的哈希值 } int main() { int n; cin>>n; for(int i=1;i<=n;i++) { scanf("%str",str+1); // 从下标1开始存 s.insert(Hash(str)); // 存储答案 } cout<<s.size(); return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。