Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

hash进阶:使用字符串hash乱搞的姿势

henry_y 2019-01-26 21:27:00 阅读数:185 评论数:0 点赞数:0 收藏数:0

前言

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

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

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

查询子串hash值

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

假设一个字符串的前缀hash值记为\(h[i]\),我们hash时使用的进制数为\(base\),那么显然\(h[i]=h[i-1]*base+s[i]\)

\(p[i]\)表示\(base\)\(i\)次方,那么我们可以通过这种方式\(O(1)\)得到一个子串的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];
}

可是为什么呢?

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

现在的目的是,取出\(l\)\(r\)这段子串的hash值,也就是说,\(h[l-1]\)这一段是没有用的,我们把在\(h[r]\)这一位上,\(h[l-1]\)这堆字符串的hash值做的左移运算全部还原给\(h[l-1]\),就可以知道\(h[l-1]\)\(h[r]\)中的hash值,那么减去即可。(简单的容斥思想)

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

题意

现在有一个字符串\(s\),每次询问它的一个子串删除其中一个字符后的hash值(删除的字符时给定的)

要求必须\(O(1)\)回答询问

Sol

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

假设我们现在询问的区间为\([l,r]\),删除的字符为\(x\)(指位置,不是字符)

类比上面的做法,我们可以先\(O(1)\)得到区间\([l,x-1]\)和区间\([x+1,r]\)的hash值,那么现在要做的事情就是把这两段拼起来了,由于我们使用的是进制hash,所以其实很简单,强行将前面的区间强行左移\(r-x\)位(这么看可能会好理解一点:\(r-(x+1)+1\))就好。

代码实现也很简单

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求最长回文子串/回文子串数

最长回文子串!我知道!马拉车!可以\(O(n)\)

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

这时候就得靠hash来水分了

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

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

单调性!我们是不是可以二分?

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

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

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

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

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

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

例题: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\n", ans + n);
}

用hash代替kmp算法

关于kmp算法,可以看pks大佬的blog,讲的真的很好!

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

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

好了,步入正题。

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

给出两个字符串\(s1\)\(s2\),其中\(s2\)\(s1\)的子串,求\(s2\)\(s1\)中出现多少次/出现的位置。

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

具体做法是预处理出来两个串的hash值,因为求的是\(s2\)\(s1\)中出现的次数,所以我们要匹配的长度被压缩到了\(s2\)的长度,所以我们只需要枚举\(s2\)\(s1\)中的起点,看看后面一段长度为\(len\)的区间的hash值和\(s2\)的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\n", ans);
}

用hash代替其他一些字符串算法

因为博主并没有写过,所以并不打算深入讲(没写过不熟悉啊...)

这一子目会分析一下hash还能代替哪些算法以及使用hash算法代替的复杂度是多少

manacher算法

求最长回文串/回文串个数manacher算法是可以做到\(O(n)\)

使用hash+二分可以做到\(O(nlogn)\),并且实现简单

kmp算法

进行单模式串匹配可以使用hash进行

复杂度\(O(n+m)\),kmp算法复杂度也是\(O(n+m)\)。但是kmp的next数组可以做到一些hash做不到的事情。

上面两个是前面两子目分析过的。

AC自动机

多模式串匹配:求文本串中各个模式串出现了多少次。

设文本串的长度为\(n\),模式串的总长度为\(len\),模式串的个数为\(m\)

hash出文本串中每个子串,并存入一个map中,复杂度是\(O(n^2logn)\)的(用map主要是便于查询)。然后hash出每个模式串,复杂度是\(O(len)\)的。

对每个模式串,查询对应的map中文本串的子串的个数即可。复杂度\(O(mlogn)\)

总复杂度是\(O(n^2logn+len+mlogn)\)

这个\(log\)可以去掉的(自行写个哈希表)。

所以并没有什么用...还是用AC自动机实在。

用AC自动机可以做到\(O(n+len)\)

后缀数组

求后缀数组中的SA数组。(如果不知道请自行百度)(给定的串为S)

最暴力的做法是直接对每个后缀进行排序,并逐字符匹配,这样会达到\(O(n^2logn)\)

那么有没有不这么无脑的做法?

有!有个hash+二分的神仙做法可以做到\(O(nlognlogn)\)

我们处理出整个串S的hash值。

在排序中对两个子串进行排序的过程中,采用二分找相同的前缀(比较用hash,可以\(O(1)\)),那么设我们最后二分到的值为r,则直接比较\(s[x+r+1]\)\(s[y+r+1]\)的大小即可(设子串1的起点为\(x\),子串2的起点为\(y\))。这样每次比较的复杂度就是\(O(logn)\)了。

加上排序,总的复杂度为\(O(nlognlogn)\)

并且其实还能求出height数组的,但是我自己对height数组的理解也不大行,所以这里就不讨论这个。

而后缀数组的复杂度是\(O(nlogn)\)(使用倍增法)

后缀数组这部分主要参考自李煜东的《算法竞赛进阶指南》。

使用hash的几个要注意的地方

在复杂度允许的情况下,尽量采用多hash(不过一般双hash就够)

比赛时能不用自然溢出就不要(平时刷题如果用自然溢出被卡可以及时换掉,但是比赛时如果用自然溢出,OI赛制就GG了)

模数用大质数这个不用说了

并且进制数不要选太简单的,比如\(233\)\(13131\)这样的,尽量大一点,比如\(13131\)\(233333\)。太小容易被卡。

以及要合理应对各种卡hash方法的最好方法就是自己去卡一遍hash,详情请参考BZOJ hash killer系列。

版权声明
本文为[henry_y]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/henry-1202/p/10324966.html

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;

支付宝红包,每日可领