演算法｜哈希从入门到精通（造福入门选手！）

作者：henry_y

链接：https://ac.nowcoder.com/discuss/178326来源：牛客网

前言

因为看各位大佬都发了一些难度较高的演算法，所以打算造福一下入门选手qwq。

求赞啊qwq想摆脱中奖绝缘体。36场没中过（在这方面即将赶上wjy神仙）。

有啥问题可以在原文评论中提出。要一模了大概就周末会上牛客吧...

其实上面说了一堆废话2333
总结一下就是你们的赞和收藏就是对我最大的肯定（废话，评论一下也是可以的2333）我想要血小板！

hash入门

首先介绍一下hash？

事实上是一种叫做蛤丝的病毒

以下讲到的hash都是OI/ACM中最常用到的hash方法：进位哈希

做法：

首先设一个进位数base，并设一个模数mod，而哈希其实就是把一个数转化为一个值，这个值是base进位的，储存在哈希表中，注意一下在存入的时候取模一下即可。

比如说现在有一个字元串orzc

枚举这个字元串的每一位，与base相乘得到ans，然后mod一下，就得到orzc的哈希值

但是哈希有一个很大的弊端：哈希冲突

什么是哈希冲突呢？

就比如说orzc的哈希值是233，而orzhjw的哈希值也是233

那么我们在查询的时候代码会认为这两个字元串是相同的，但显然这两个字元串是不同的

减少哈希冲突的方法很多

自然溢出法，双哈希之类的

看一道例题理解一下

洛谷P3370 【模板】字元串哈希

事实上如果理解了刚刚讲的hash的原理的话，这道题就很水了，因为本来就是模板题

用一段hash的代码再来巩固一下刚才的知识

#define base 233 #define inf 1<<30 ull mod=inf; //定义一个大数(最好是质数)作为模数，这里用的是1<<30 //定义一个base进位，这里是233 il ull hash(char s[]){ ll ans=0,len=strlen(s); for(ll i=0;i<len;i++){ ans=(base*ans+(ull)s[i])%mod; } return ans; //枚举该字元串的每一位，与base相乘，转化为base进位，加(ull)是为了防止爆栈搞出一个负数，(ull)是无符号的，但其实加了一个ull是可以不用mod的，加个mod更保险 //然而加了mod会很玄学，莫名比不加mod慢了300多ms }

因为懒就没有去找一个大质数来当mod，用了1<<30代替，但是最好还是找一个大质数当mod（搜索一下生日悖论？大概就会明白原因了）

最后贴一下刚刚的例题的两种解法：

解法1：单hash/自然溢出法

这里就当一种解法来说吧

因为代码差异不大

这道题的话单hash mod开大质数是可以过的，但是在大多数难一些的题目里面是会被卡掉的

#include <cstdio> #include <cstring> #include <algorithm> #define ll int #define inf 1<<30 #define mt(x,y) memset(x,y,sizeof(x)) #define il inline #define ull unsigned long long il ll max(ll x,ll y){return x>y?x:y;} il ll min(ll x,ll y){return x<y?x:y;} il ll abs(ll x){return x>0?x:-x;} il ll swap(ll x,ll y){ll t=x;x=y;y=t;} il void read(ll &x){ x=0;ll f=1;char c=getchar(); while(c<0||c>9){if(c==-)f=-f;c=getchar();} while(c>=0&&c<=9){x=x*10+c-0;c=getchar();} x*=f; } using namespace std; #define N 10001 #define base 233 ull mod=212370440130137957ll; ll f[N],n; char a[N]; //ull hash(char s[]){ ll ans=0,len=strlen(s); for(ll i=0;i<len;i++){ ans=((base*ans+(ull)s[i])+mod)%mod; } return ans; } //这个是单hash+大质数mod，也是可以过的，但是会比较慢 ull hash(char s[]){//自然溢出 ull ans=0,len=strlen(s); for(ll i=0;i<len;i++){ ans=base*ans+(ull)s[i]; //这里不使用mod让它自然溢出，定义为ull的数在超过2^32的时候会自然溢出 //如果把这个换成上面的hash就会400ms+ //所以说自然溢出大法好 } return ans; } int main(){ read(n); for(ll i=1;i<=n;i++){ scanf("%s",a); f[i]=hash(a); } sort(f+1,f+n+1);ll ans=1; for(ll i=1;i<n;i++){ if(f[i]!=f[i+1])ans++; } printf("%d ",ans); return 0; }

解法2：双hash

其实就是用两个不同的mod来算hash，哈希冲突的概率是降低了很多，不过常数大，容易被卡，这道题要700ms+

本人还是更推荐自然溢出法

#include <cstdio> #include <cstring> #include <algorithm> #define ll int #define inf 1<<30 #define mt(x,y) memset(x,y,sizeof(x)) #define il inline #define ull unsigned long long il ll max(ll x,ll y){return x>y?x:y;} il ll min(ll x,ll y){return x<y?x:y;} il ll abs(ll x){return x>0?x:-x;} il ll swap(ll x,ll y){ll t=x;x=y;y=t;} il void read(ll &x){ x=0;ll f=1;char c=getchar(); while(c<0||c>9){if(c==-)f=-f;c=getchar();} while(c>=0&&c<=9){x=x*10+c-0;c=getchar();} x*=f; } using namespace std; #define N 10001 #define base 233 ull mod1=212370440130137957ll; ull mod2=inf; ll n; char a[N]; struct node{ll x,y;}f[N]; il ull hash1(char s[]){ ll ans=0,len=strlen(s); for(ll i=0;i<len;i++){ ans=(base*ans+(ull)s[i])%mod1; } return ans; } il ull hash2(char s[]){ ll ans=0,len=strlen(s); for(ll i=0;i<len;i++){ ans=(base*ans+(ull)s[i])%mod2; } return ans; } il bool cmp1(node a,node b){return a.x<b.x;} il bool cmp2(node a,node b){return a.y<b.y;} int main(){ read(n); for(ll i=1;i<=n;i++){ scanf("%s",a); f[i].x=hash1(a); f[i].y=hash2(a); } sort(f+1,f+n+1,cmp1);sort(f+1,f+n+1,cmp2); ll ans=1; for(ll i=1;i<n;i++){ if(f[i].x!=f[i+1].x||f[i].y!=f[i+1].y)ans++; } printf("%d ",ans); return 0; }

这道题也是可以打字典树的，也是裸的做法，读者也可以尝试一下，因为这里是讲hash的所以就不放字典树的代码了

hash进阶：使用字元串hash乱搞的姿势

主要介绍hash的各种乱搞方法，hash入门请参照我之前这篇文章

不好意思hash真的可以为所欲为

在开头先放一下题表（其实就是我题解中的hash题目qwq）

查询子串hash值

必备的入门操作，因为OI中用到的hash一般都是进位哈希，因为它有一些极其方便的性质，比如说，是具有和前缀和差不多的性质的。

假设一个字元串的前缀hash值记为，我们hash时使用的进位数为，那么显然记表示的次方，那么我们可以通过这种方式得到一个子串的hash值（设这个子串为s[l]...s[r])

typedef unsigned long long ull; ull get_hash(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }

可是为什么呢？

我们知道，进行进位哈希的过程本质上就是把原先得到的哈希值在进位上强行左移一位，然后放进去当前的这个字元。

现在的目的是，取出到这段子串的hash值，也就是说，这一段是没有用的，我们把在这一位上，这堆字元串的hash值做的左移运算全部还原给，就可以知道在中的hash值，那么减去即可。（简单的容斥思想）

这是基本操作，现在来看一个这个的拓展问题。

题意

现在有一个字元串，每次询问它的一个子串删除其中一个字元后的hash值（删除的字元时给定的）

要求必须回答询问

Sol

删除操作？那不能像上面那样子简单粗暴的来搞了，但是其实本质上是一样的。

假设我们现在询问的区间为，删除的字元为（指位置，不是字元）

类比上面的做法，我们可以先得到区间和区间的hash值，那么现在要做的事情就是把这两段拼起来了，由于我们使用的是进位hash，所以其实很简单，强行将前面的区间强行左移位（这么看可能会好理解一点：）就好。

代码实现也很简单

typedef unsigned long long ull; ull get_hash(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; } ull get_s(int l, int r, int x) { return get_hash(l, x - 1) * p[r - x] + get_hash(x + 1, r); }

这题的原题是LOJ#2823. 「BalticOI 2014 Day 1」三个朋友，需要分类讨论一下，不过知道上面这个也就不难了

用hash求最长回文子串/回文子串数

最长回文子串！我知道！马拉车！可以！

可是如果你马拉车写挂了呢？或者像我一样不会马拉车

这时候就得靠hash来水分了

我们知道，回文子串是具有单调性的

如果字元串s[l...r]为回文子串，那么s[x...y](l<x,y<r)也一定是回文子串

单调性！我们是不是可以二分？

我们暂时只讨论长度为奇数的回文子串。（事实上，长度为偶数的回文子串与奇数的只是处理上的一些细节不同，仅此而已）

考虑枚举回文子串的中点，并二分回文子串的长度（不过一般来说，二分回文子串的长度的1/2可能会更好写一点），那么我们使用上文提到的查询子串hash值的方法，就可以判断二分得到的这个子串是不是回文子串了。

对于长度为偶数的回文子串，枚举中点左边/右边的字元即可

效率是的，复杂度较马拉车演算法比较逊色，不过如果马拉车演算法打挂或者是时间复杂度允许的情况下，hash也是一个不错的选择。

然后还有一种方法，适合像我这种下标总是搞错的，可以直接处理出正串和反串的hash值，然后每次根据二分出来的长度计算整个字元串的起止，判断正串和反串的hash值是否相等即可。（这样就不用研究恶心的下标了...研究下标还得分奇偶讨论...）

字元串的很多特性是具有单调性的，二分求解是一个常见的思路，配合哈希进行判断操作一般可以做到在 效率内完成问题

例题：SP7586 NUMOFPAL - Number of Palindromes

练习：LOJ#2452. 「POI2010」反对称 Antisymmetry

例题代码

#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; #define N 10100 #define base 13131 char s[N]; ull h1[N], p[N], h2[N], ans = 0; int n;

ull gh1(int l, int r) { return h1[r] - h1[l - 1] * p[r - l + 1]; }
ull gh2(int l, int r) { return h2[l] - h2[r + 1] * p[r - l + 1]; }

ull query1(int x) { //奇
int l = 1, r = min(x, n - x);
while(l <= r) {
int mid = (l + r) >> 1;
if(gh1(x - mid, x + mid) == gh2(x - mid, x + mid)) l = mid + 1;
else r = mid - 1;
}
return r;
}

ull query2(int x) { //偶
int l = 1, r = min(x, n - x);
while(l <= r) {
int mid = (l + r) >> 1;
if(gh1(x - mid + 1, x + mid) == gh2(x - mid + 1, x + mid)) l = mid + 1;
else r = mid - 1;
}
return r;
}

int main() {
scanf("%s", s + 1); p[0] = 1;
n = strlen(s + 1);
for(int i = 1; i <= n; ++i) {
h1[i] = h1[i - 1] * base + s[i];
p[i] = p[i - 1] * base;
}
for(int i = n; i; i--) h2[i] = h2[i + 1] * base + s[i];
for(int i = 1; i < n; ++i) {
ans += query1(i) + query2(i);
}
printf("%llu
", ans + n);
}

用hash代替kmp演算法

关于kmp演算法，可以看pks大佬的blog，讲的真的很好！

但是我们这里不讲kmp演算法，我们利用hash来代替kmp演算法求解单模式串匹配问题。

但是kmp演算法的next数组真的很妙！可以解决很多神奇的东西，强烈推荐去学学！

好了，步入正题。

单模式串匹配问题是什么？

给出两个字元串和，其中为的子串，求在中出现多少次/出现的位置。

如果有认真看过该篇文章的第一子目的话，应该不难想到这题的hash做法。

具体做法是预处理出来两个串的hash值，因为求的是在中出现的次数，所以我们要匹配的长度被压缩到了的长度，所以我们只需要枚举在中的起点，看看后面一段长度为的区间的hash值和的hash值一不一样就好。

时间复杂度是O(n+m)的！和kmp演算法一样！

例题：LOJ #103. 子串查找 (本来想放洛谷的结果要输出next数组就没办法了23333)

练习：UVA10298 Power Strings

例题代码

#include <bits/stdc++.h> using namespace std;

#define N 1000010
#define ull unsigned long long
#define base 233

ull h[N], p[N], ha;
char s1[N], s2[N];

int main() {
scanf("%s%s", s1 + 1, s2 + 1);
int n = strlen(s1 + 1), m = strlen(s2 + 1);
for(int i = 1; i <= m; ++i) ha = ha * base + (ull)s2[i];
p[0] = 1;
for(int i = 1; i <= n; ++i) {
h[i] = h[i - 1] * base + (ull)s1[i];
p[i] = p[i - 1] * base;
}
int l = 1, r = m, ans = 0;
while(r <= n) {
if(h[r] - h[l - 1] * p[m] == ha) ++ans;
++l, ++r;
}
printf("%d
", ans);
}