1 Star 0 Fork 1

tzj/算法笔记

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
哈希.txt 3.63 KB
一键复制 编辑 原始数据 按行查看 历史
tu 提交于 2023-04-04 20:45 . 第一次整体提交
拉链法,如果映射值相同时,就是拉出一个链表全部存下来。
拉链法
acwing 模拟散列表
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10;
int e[N],h[N],ne[N],idx;
void Insert(int x)
{
int k=(x % N + N) % N;
e[idx]=x;
ne[idx]=h[k];
h[k]=idx;
idx++;
}
bool Query(int x)
{
int k=(x % N + N) % N;
for(int i=h[k];i!=-1;i=ne[i])
{
if(e[i]==x)
return true;
}
return false;
}
int main()
{
int n;
scanf("%d",&n);
memset(h,-1,sizeof h);
while(n--)
{
char op[2];
int x;
scanf("%s%d",op,&x);
if(op[0]=='I')
Insert(x);
else
{
if(Query(x))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}
return 0;
}
开放寻址法,如果映射值相同时,就往后找一个空的坑填上,
一般只需要开题目范围的2-3倍的大小。
开放寻址法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 2e5+10 , INF = 0x3f3f3f3f;
int h[N];
int find(int x)
{
int t = (x % N + N) % N;
while (h[t] != INF && h[t] != x)
{
t ++ ;
if (t == N)
t = 0;
}
return t;
}
int main()
{
memset(h, 0x3f, sizeof(h));
int n;
scanf("%d", &n);
while (n -- )
{
char op[2];
int x;
scanf("%s%d", op, &x);
if (op[0 ] == 'I')
h[find(x)] = x;
else
{
if (h[find(x)] == INF)
puts("No");
else
puts("Yes");
}
}
return 0;
}
字符串哈希(字符串前缀哈希法)
核心思想与应用
1. 应用
利用字符串前缀哈希方法快速判断同一个字符串两个不同区间是否相等;
如果hash值相等等价于两个区间相同;否则两个区间不等
2. 处理步骤
step1: 把字符串看成P进制数
step2:预处理字符串所有的前缀hash值, hash[i] = (hash[i - 1] * P + str[i]) mod Q,
这里P一般取131或者13331,Q取2^64
step3: 计算区间hash值hash[l, r] = hash[r] - hash[l-1] * p[r - l + 1]
代码注意点
由于 Q取2^64次方,可以直接用 unsigned long long存取 h[N]、p[N]
计算区间时候需要用到 P的 n次方,需要预处理,特别注意 p[0] = 1
代码模板
const int N = 100010;
const int P = 131;
ULL h[N], p[N];
ULL get(int l, int r)
{
return h[r] - h[l-1] * p[r - l + 1];
}
p[0] = 1;
for(int i = 1; i <= n; i++)
{
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + str[i-1];
}
字符串哈希
1,不能映射成0
2,映射成p进制数 经验p取值131或13331 Q取值2^64
公式:h[r]-h[l-1]*p^(r-l+1)
acwing 字符串哈希
#include<iostream>
using namespace std;
typedef unsigned long long ull;
const int P=131;
const int N=1e5+10;
ull h[N],p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
char str[N];
//计算子串str[l~r]的哈希值
ull get(int l,int r)
{
return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
int n,m;
scanf("%d%d%s",&n,&m,str);
p[0]=1; //初始化
for(int i=1;i<=n;i++) //初始化
{ //初始化
p[i]=p[i-1]*P; //初始化
h[i]=h[i-1]*P+str[i]; //初始化
} //初始化
while(m--)
{
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
if(get(l1,r1)==get(l2,r2))
puts("Yes");
else
puts("No");
}
return 0;
}
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
C++
1
https://gitee.com/tu-zhenjin/algorithm-notes.git
git@gitee.com:tu-zhenjin/algorithm-notes.git
tu-zhenjin
algorithm-notes
算法笔记
master

搜索帮助