学长来讲了hash，感觉好香
哈希算法
算法概况
hash是一种思想 是一种广义的算法 不懂的可以百度
而我们常将哈希的思想用在字符串中 用于O(1) 判断给出的两个字符串是否相等（预处理完的情况下）
例题&算法
这里结合例题理解一下：
给出两个字符串A与B 每次询问给出l,r,s,t 判断A[l...r] 与 B[s...t]是否相等
如果我们用裸的暴力的话 显然对于每次询问我们都要用O(n) 的效率 所以对于m次询问效率是O(nm)但是我们用hash可以很轻松的解决这个问题
关于一个字符串我们很显然是无法直接O(1)比较的 但是对于一个数字可以 所以我们可不可以把一个字符串转化为数字呢？
答案是肯定的
- 首先我们存入一个字符串 然后通过把字符串转化为ASCII码值 然后就可以把字符串转化为数字了
- 因此我们定义一个数组f[i]表示当前字符串的第i位 的前缀和 （类似前缀和），那么f[i] 的求法如下
for(int i = 1;i <= strlen(s1+1);++i){
f1[i] = f1[i-1] * base + s1[i] - 'a' + 1;
}
-
注意我们这里用到了base base其实是自己定义的一个进制位 可以自己随意定义，根据题目自己定义，大小自己定，为了防止出现两个不同的字符串存成相同的值
-
因此这样我们就处理出了前缀和，那么对于取区间的问题 显然不能像普通的前缀和那样直接减 所以我们又要用到一个pw数组，用来辅助我们求区间和
pw[0] = 1;
for(int i = 1;i <= strlen(s1+1);++i){
pw[i] = pw[i-1] * base;
}
下面给出例题代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
const int base = 223;
int pw[maxn],f1[maxn],f2[maxn];
char s1[maxn],s2[maxn];
int main(){
scanf("%s%s",s1+1,s2+1);
for(int i = 1;i <= strlen(s1+1);++i){
f1[i] = f1[i-1] * base + s1[i] - 'a' + 1;
}
pw[0] = 1;
for(int i = 1;i <= strlen(s1+1);++i){
pw[i] = pw[i-1] * base;
}
for(int i = 1;i <= strlen(s2+1);++i){
f2[i] = f2[i-1] * base + s2[i] - 'a' + 1;
}
int m;scanf("%d",&m);
while(m--){
int l1,r1,l2,r2;scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
if((f1[r1] - f1[l1 - 1] * pw[r1 - l1 + 1]) == (f2[r2] - f2[l2 - 1] * pw[r1 - l1 + 1]))printf("YES
");
else printf("fake u**
");
}
return 0;
}
哈希表
算法概况：
关于一个较大的值域 我们希望在较短的时间内完成查询操作 但是值域太大导致不能用计数数组 （你又懒得用离散化） 就可以用哈希表来处理了
例题导入
对于这样一个数列 {1,75,324,43,1353,91,40}
我们想要查询一个数字 可以选择开一个数组a[7] 然后将这几个数字都存进去
然后如果要查询的话 显然会是O(n) 的效率 如果加上各种奇淫巧技应该还可以再优化到(log_n)吧
但是我们也可以选择开一个数组a[1353] 然后将数值作为下标 数组保存出现几次
这样我们要查询某个数字出现次数就是O(1)的效率
显然我们的效率提高了很多 但是看看我们的空间 ……………………………………（泪目就完了）
所以这时我们哈希表闪亮登场
- 我们一开始将数值作为下标 很显然我们有很多地方是没有被用到的 比如a[2] a[3] 都是浪费的空间
- 那么我们可以选择让这个数值取上一个数的模 然后将这个新值作为数组下标
- 举个栗子: 我们这个题可以选择将7作为模数 取完模之后显然数值范围为0～6 而0很特殊 所以我们避免掉0的情况 让数值取模之后+1
- 这样我们的数值范围就变成了1～7 然后开始存数
- 1存进a[1],75存进a[5]，324存进a[2]，43存进a[1] 诶 a[1]存了俩值 vvvvvvvvv
- 所以显然这样出现了两个不同的数值x,y 但是会出现x ≡ y (mod p) 这就是我们常说的哈希冲突
- 如何处理冲突呢？ 我们选择不再将数组存数值 而是存一个链表（和最短路的基本一样 木得学过最短路的同鞋emmm 你想起啥来看哈希的）
- 所以我们的算法模板就有了
板子
背景 ：
- 你有一个序列（别问，问就是我给你的），里面有n个数，有m次查询，询问当前数在序列中出现了多少次
- 第一行输入两个整数n,m 表示有n个数 ，m次询问
- 第二行输入 n 个数字 表示这个序列中的数字
- 第三行输入 m 个数字 询问当前数字在序列中出现次数
- 请根据每次询问给出对应的答案
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
const int mod = 223;//模数
struct node{//邻接表
int val,cnt,next;
}a[maxn];
int head[maxn],tot;
void add(int x){
int now = x % mod + 1,u = head[now];//now为哈希操作之后对应的值 u表示链头
for(;u;u = a[u].next)//遍历整个链表
if(a[u].val == x){//如果找到当前值
a[u].cnt++;break;
}
if(!u){//如果链表遍历完仍然为找到对应的值
a[++tot].val = x;//开个新点
a[tot].cnt = 1;
a[tot].next = head[now];
head[now] = tot;
}
}
int ask(int x){
int now = x % mod + 1;
for(int i = head[now];i;i = a[i].next)if(a[i].val == x)return a[i].cnt;//查找到了对应的值
return 0;//没有查找到对应的值
}
int main(){
int n,m;scanf("%d%d",&n,&m);
while(n--){
int x;scanf("%d",&x);
add(x);
}
while(m--){
int x;scanf("%d",&x);
printf("%d
",ask(x));
}
return 0;
}