定义
散列是一种数据处理方法, 通过 散列函数 将原数据生成为一种更易于存储的数据。使用散列表可以提高比较数据的效率。
散列函数: 将原数据传给它并进行处理, 处理完成后返回。
冲突: 当两个不同的数据经过处理后产生了相同的散列函数值, 这是称散列函数发生了冲突。
理想情况下散列函数是双射 (字符串和整数一一对应), 但显然无法实现。
最低要求: 字符串确定后, 能唯一确定它的哈希值。
构造方法:
\(hash(s)=(s_1\times seed^{|s|-1}+s_2\times seed^{|s|-2}+...+s_{|s|}\times seed^0)\),其中seed和mod是常数, mod是较大的质数。
计算子串的hash值
先计算出前缀的hash值：
\(hash_i=hash(pre(s,i))=(s_1\times seed^{i-1}+s_2\times seed^{i-2}...+s_i\times seed^0)%mod\)
对于子串 \(s_{l,r}\) , 其hash值为 \(hash_r-hash_l\times seed^{r-l}\)
例题: POJ3461
简要题意: 查找某个子串在字符串中出现了多少次。
hash模板题, 需要注意为了方便查询子串, hash值应倒着计算
详情见代码。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef unsigned long long ll; //ull自然溢出取模
const int maxn=1e6+10,base=31;
ll hashh[maxn],xp[maxn];
char a[maxn],b[maxn];
int main(){
int t; scanf("%d",&t);
xp[0]=1;
for(int i=1;i<=maxn;i++)
xp[i]=xp[i-1]*base;
while(t--){
memset(a,0,sizeof(a));
memset(b,0,sizeof(b)); //记得数组清空
scanf("%s%s",&a,&b);
int l=strlen(a),n=strlen(b);
ll sub=0; int ans=0; hashh[n]=0;
for(int i=l;i>=0;i--)
sub=sub*base+a[i];
for(int i=n-1;i>=0;i--)
hashh[i]=hashh[i+1]*base+b[i];
for(int i=0;i<=n-l;i++)
if(sub==hashh[i]-hashh[i+l]*xp[l]) ans++;
printf("%d\n",ans);
}
return 0;
}
为方便实现我们还可以用 unordered_set 或 unordered_map存储链式哈希。
例题: 调皮的小biu
题目描述
小 \(biu\) 的期中考试刚刚结束，调皮的小 \(biu\) 不喜欢学习，所以他考试中抄袭了小 \(piu\) 的试卷。
考试过程中一共有 \(n\) 道题目，每道题目的标准答案为区间 \([1,5]\) 中的一个正整数。
现在有小 \(biu\) 和小 \(piu\) 的答案序列为 \(a\) 和 \(b\) , 现在老师想知道两个答案序列最长相等的连续子串的长度是多少。
输入格式
第 \(1\) 行: 一个正整数 \(n\) 表示题目个数;
第 \(2\) 行: \(n\) 个正整数, 第 \(i\) 个数表示 \(a_i\);
第 \(3\) 行: \(n\) 个正整数, 第 \(i\) 个数表示 \(b_i\);
输出格式
输出一个正整数表示两个序列的最长相等子串的长度。
输入样例
10
1 1 2 1 2 1 2 1 1 5
3 3 2 3 1 2 1 1 3 4
输出样例
4
思路
用hash预处理再二分答案, 应用了unordered_set.
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int mx=1e5+5;
int a[mx],b[mx],n;
ull h1[mx],h2[mx],p1[mx],p2[mx];
unordered_set<ull>st;
bool check(int x){
st.clear();
int l,r;
for(int i=1;i+x-1<=n;i++){
l=i,r=i+x-1;
ull tmp=h1[r]-h1[l-1]*p1[r-l+1];
st.insert(tmp);
}
for(int i=1;i+x-1<=n;i++){
l=i,r=i+x-1;
ull tmp=h2[r]-h2[l-1]*p2[r-l+1];
if(st.find(tmp)!=st.end()) return true;
}
return false;
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
p1[0]=1; p2[0]=1;
for(int i=1;i<=n;i++){
cin>>a[i];
h1[i]=h1[i-1]*1331+a[i];
p1[i]=p1[i-1]*1331;
}
for(int i=1;i<=n;i++){
cin>>b[i];
h2[i]=h2[i-1]*1331+b[i];
p2[i]=p2[i-1]*1331;
}
int l=1,r=n,mid;
while(l<=r){
mid=l+r>>1;
if(check(mid)) l=mid+1;
else r=mid-1;
}
cout<<r;
return 0;
}