21Hash在信息学竞赛中的一类应用.docx

21Hash在信息学竞赛中的一类应用.docx

《21Hash在信息学竞赛中的一类应用.docx》由会员分享，可在线阅读，更多相关《21Hash在信息学竞赛中的一类应用.docx（16页珍藏版）》请在冰点文库上搜索。

21Hash在信息学竞赛中的一类应用

Hash在信息学竞赛中的一类应用

【正文】

Hash表作为一种高效的数据结构，有着广泛的应用。

如果Hash函数设计合理，理想情况下每次查询的时间花费仅仅为O（h/r），即和Hash表容量与剩余容量的比值成正比。

只要Hash表容量达到实际使用量的大约1.5倍以上，查询花费的时间基本就可以认为恒为O

（1）。

对于一个Hash表，一个好的Hash函数是尤其重要的，因为它能使Hash表保证效率。

一个好的Hash函数最显而易见的特征是，能使不相同的东西经过Hash之后只有很小的几率相同。

这样能避免过多冲突的产生。

Hash表离不开Hash函数，但是反过来呢？

有的时候，Hash函数却是可以离开Hash表的。

一个常见的例子就是著名的MD5算法，它是一个Hash函数，但是它的用途往往是对信息进行加密，以验证信息的正确性。

换句话说，我们事实上是通过直接比较MD5算出的结果是否相同以推断原文内容是否一致。

除了MD5，常用的CRC32校验码和SHA-1算法也是基于类似的想法而产生的。

那么，信息学竞赛中，这样的算法有没有用武之地呢？

本文要讨论的，就是这一类以判重或判等价为目标的Hash函数。

让我们来看看例题1。

例题1多维匹配

题目大意

在一个串中求另一个串第一次出现的位置，很简单，KMP即可。

扩展到二维情况，就是求在一个矩阵中求另一个矩阵第一次出现的位置。

而如果扩展到k维的情况，又该怎么做呢？

待匹配数组X各维的尺寸为N1，N2，…，Nk，模式数组Y各维的尺寸为M1，M2，…，Mk。

记N=N1N2…Nk，M=M1M2…Mk。

保证k≤10，Ni≥Mi，而N和M都不超过500000。

算法分析

本题常见的算法是多维情况的KMP，先算1维时的匹配情况，然后处理2维，3维……直到N维时的情况。

时间复杂度为O（k*（N+M））。

但是它难以理解和记忆，也不容易在比赛中的短短几个小时完成和写对。

朴素的解法相对易于实现，但是使朴素算法很容易想到，而且针对数据又很容易制作，因此只有在完全没有思路的时候才值得一试。

有没有第三种选择呢？

答案是肯定的。

朴素的解法相当于枚举了每个起点（起点数量显然不会超过N）并加以判断，然而判断两个子数组是否相同的时间复杂度高达O（M），这就是导致朴素算法在遇到针对数据的情况下很慢的原因。

能不能在比较两个子数组之前先快速地排除一些明显不可能的情况呢？

由于很容易构造出仅有一个字符不同的数据，不管采用什么顺序比较都会消耗大量的时间。

Hash函数在这里派上了用场。

我们可以对每个尺寸与模式数组一样的子数组计算一个Hash值。

显然，只有当某个子数组的Hash值与模式数组的Hash值一样，它们才值得比较。

多维的KMP要从1维的情况开始考虑，并推广至高维。

那么这种计算Hash函数的匹配算法我们也可以先考虑一维的情况——就是Rabin-Karp算法。

对于一个字符串S，可以使用这个函数求出其Hash值：

那么，模式串Y的Hash值就可以轻松地求出。

记待匹配串X从第i个字符开始的长度为M的子串为Si，则不难发现f（Si+1）和f（Si）的关系：

换个角度，如果不考虑modq，这个函数就是把字符串看作一个p进制数求出的值，这样，Xi+1就是Xi“左移”一位，然后去掉最前面一位，再加上右面新进来的一位得到的。

因此上面的递推公式也是显然的。

有了这个递推公式，不难在线性时间内求出X的所有长度为M的子串的Hash值。

现在把问题扩展到高维的情况。

不难发现要计算的Hash值的个数仍然不超过N个，可见，只要有合适的递推方法，仍然可以在线性时间内求出所有子矩阵的Hash值。

事实上，一个M1行，M2列的子矩阵可以被看作是M2个“竖条”组成的一个串。

我们可以先把每个长度为M1的“竖条”计算出一个Hash值，然后再计算二维情况的Hash值。

需要注意的一点是，在计算一维的Hash值（“竖条”的Hash值）和计算二维的Hash值时使用的b值不能一样，不然不难想到下面反例：

它们并不相同，但是Hash的结果肯定一样。

这就违背了使用Hash的初衷。

因此，在第一维的计算和第二维的计算中要使用不同的p值。

二维情况时，求出所有长度为M1的“竖条”所需要花费的时间是O（N）的，然后把这些竖条的Hash值看作“字母”计算横向的Hash值（即各个子矩阵的Hash值），所花费的时间也是O（N）的。

总时间复杂度仍然是O（N）的。

二维情况的Hash函数为（len1（S）和len2（S）分别表示S在两个维度上的大小）：

类似地，记待匹配矩阵X从第i1行，第i2列为左上角的M1行，M2列的子矩阵为

，我们有递推式：

式中

和

都是一维情况下的Hash值，即预先计算出的“竖条”的Hash值。

扩展到k维情况，则不难想到，先算出所有尺寸为M1×M2×…×Mk-1的子数组的Hash值，再使用类似上面的办法把这些尺寸为M1×M2×…×Mk-1的子数组的Hash值看作一个个字符而使用Rabin-Karp的Hash函数计算出各个尺寸为M1×M2×…×Mk的子数组的Hash值。

可见，需要k轮计算就可以算出所有尺寸为M1×M2×…×Mk的子数组的Hash值，时间复杂度为O（kN+M）。

k维时的Hash函数：

类似地可以推出递推式

如果没有最后的modq操作，那么这个Hash函数可以理解成一个进制转换，当每次的p都取得比当时的字符集还要大的时候，只要Hash值不同就一定能确定内容不同。

但是事实上计算出来的Hash值就会大到使这个算法没有意义的程度（比较这个“Hash值”的速度不会比直接比较更快），因此取余是必须的。

一个理想情况下的Hash函数，如果能产生S种不同的值，那么对两个不一样的子数组算出一样的值的可能性就只有1/S。

我们的Hash函数当然未必能达到理想情况，但是由“1/S”这个式子不难想到，加大S就能有效地减少判错的可能性。

并且还能得出另一个结论：

如果一个Hash函数的精确程度不够，只需要再计算一个与之不同的Hash函数，就可以有效地提高正确率！

当然，在本题中，时间复杂度已经近似于（因为毕竟这个Hash函数不是理想的Hash函数）O（kN+N*（1/S）*M）了。

S只要大小不比N/k小，后一项就不是时间复杂度的瓶颈了，也没有必要在这方面下太大功夫。

反而，如果计算多个Hash函数，会显著增加算法的常数。

关于p和q的取值，由于可以理解成一个p进制的转换，再对q取余，应当在范围允许的情况下尽量避免冲突，建议：

1、p不宜过小，不然很容易出错。

2、q可以取一个质数，然后p选取一个能使对于所有1至p-2的i，pimodq≠1。

这个Hash函数不但可以这样滚动计算，也可以采用分段，分块，线段树等办法计算和维护，具体的一些办法可以参见后面的一些例题。

例题2Equalsquares（Ural1486）

题目大意

在一个N×M的字符矩阵中找到两个相同的子正方形矩阵（可以相交），并使找到的两个子正方形矩阵的边长尽量大。

算法分析

有了例题1的经验，在面对本题的时候不难想到，二分查找正方形的边长，然后使用一个Hash表来判断该边长是否可行。

Hash函数与例题1的二维情况一致。

时间复杂度是O（NMlog（N*M））的。

但是不幸的是，本题时间限制很严，这样做的程序依然会超时。

最后在使用一个看上去有点冒险的改动之后，终于通过了本题：

直接检查是否产生了相同的Hash函数，如果存在相同的Hash函数，则认为该边长可行，否则即认为它不可行。

这道题目就这样通过了，但是这样的改动是不是太冒险了一点呢？

事实上，两个子正方形的内容不同而Hash值相同的可能性很小。

所以，一般情况下我们可以认为，如果Hash值相同，则原内容相同。

这里还有一个问题：

Hash表存放了什么？

如果存放的是Bool而不使用位压缩，则似乎浪费了不少空间，而且Hash表不可能开到很大，因此两个不同的内容Hash到同一个位置还是有可能的，简单地比较“这个位置是否被Hash到”仍然不算保险，毕竟，一次查询有100万分之一的可能性出错的话，100万次查询出错概率就很可观了。

这里介绍的一个小技巧是计算两个Hash值，一个用于确定Hash表中的位置，另一个则用于比较。

这样，只有如果在Hash表的某个地址开始查找找到了一个Hash值与自己的Hash值一样的元素，才认为自己在Hash表中出现过。

例题3不稳定匹配

题目大意

有两个串A和B，每次可以进行的操作有：

INSERTij：

在A中第i个字符前插入j。

DELETEi：

删除A中第i个字符。

REVERSEij：

把A中i到j之间的内容反转。

QUERYij：

求A从第i个字符开始，B从第j个字符开始能匹配的最大长度，即询问A从第i个字符开始的后缀与B从第j个字符开始的后缀的LCP长度。

算法分析

如果两个串不会变化，求LCP只需要求出A+B的后缀数组即可。

但是本题的A串是不断变化的，而且由变化的方式可以看出，每次操作都会导致后缀数组发生很大的变化，因此我们应该另辟蹊径。

对于一个k，不难判断两个串的LCP是否有至少k个字符：

计算这两个串的前k个字符的Hash值，并且比较它们是否相等。

如果相等，就几乎可以肯定地认为这两个串的LCP至少有k个字符，否则，它们的LCP长度肯定不到k。

这样，就可以通过二分查找来计算LCP。

现在问题又转化成了怎么求一个子串的Hash。

不妨仍然采用Rabin-Karp的Hash函数，如果已知了S1和S2的Hash值，不难求出S1+S2的Hash值：

而

的Hash值显然又是可以在O（n）时间内预处理的得到的。

因此，可以在O

（1）时间内通过两个字符串的Hash值得到它们连接后得到的串的Hash值。

因此，可以使用块状链表维护计算A中子串的Hash值，方法于维护计算部分和类似，不同之处在于一个字符串正向和反向的Hash值是不同的，为了能在O（n0.5）时间内完成reverse操作，应当要能在O

（1）时间内把一个块“反转”，这就要求我们为一个块维护两个Hash值：

一个是正向的，一个是倒向的。

除此之外的操作于维护部分和或者维护最大值类似。

这样，插入，删除，反转操作是O（n0.5）的，而查询操作是O（n0.5logn）的。

类似地，本题的另一种解法是在一棵splay树上维护Hash值。

每次一个节点被旋转或以它为根的子树被修改时，则计算它的正向Hash值和反向Hash值，这样，就可以在O

（1）时间你reverse一棵子树，通过split可以不难地把一棵子树在均摊O（logn）时间内反转。

插入，删除操作显然也是均摊O（logn）的，而查询操作的均摊时间复杂度为O（log2n）。

例题4一类同构判定的问题

问题1：

比较两棵树是否相同。

不难想到的算法是使用两个字符串分别表示两棵树，但是如果使用Hash的话应该怎么做呢？

可以使用一种类似树状递推的方法来计算Hash值：

对于一个节点v，先求出它所有儿子节点的Hash值，并从小到大排序，记作H1，H2，…，HD。

那么v的Hash值就可以计算为：

换句话说，就是从某个常数开始，每次乘以p，和一个元素异或，再除以q取余，再乘以p，和下一个元素异或，除以q取余……一直进行到最后一个元素为止。

最后把所得到的结果乘以b，再对q取余。

之所以事先对儿子的Hash值进行排序，是因为仅仅儿子的顺序不同并不会导致树的不同，而后面如何Hash就比较随意了，即使不用这个Hash函数，只要使用一个效果足够好的Hash函数也是可以的。

但是要注意，诸如Rabin-Karp的那个Hash函数就不适合在这里应用，因为不难找到反例：

 考虑右边的树的儿子的顺序如图所示的情况（可以认为Hash函数的大小是随机分布的，因此有一半的可能性出现这种情况），由于叶子节点的Hash值必然相同（因为都是等价的），不妨记作l，然后递推关系是：

则左边的树的Hash值为：

右边为：

不难看出他们是相等的，而两棵树是不相等的。

类似地，前面的计算方法如果最后不乘以b，也是错的（可以分析树退化成线形的情况）。

那么，既然直接比较Hash值肯定是有概率出错的，为什么还要指出哪些Hash函数适用，哪些不适用呢？

有的错误是“偶然误差”，不改变Hash的计算方法，仅仅改变p等常数即可消除，而有的则是“系统误差”，是这个Hash函数本身的不合理导致的，后一种情况应尽量避免出现。

当然，在比赛的短短几个小时中未必能够判断这个Hash函数究竟合不合理，但是尽量选择在不确定p,q等可以改变的常数的情况下难以构造反例的Hash函数会是比较好的办法。

现在，只需要比较两棵树的Hash值，即可分辨它们是否相同。

时间复杂度为O（nlogn）。

还有另一种Hash函数也能解决这个问题，而且对于解决下一个问题很有帮助：

考虑把这棵树使用一个串表示出来（类似最小表示），然后计算那个串的Hash值。

当然，如果真的像最小表示法那样把字符串弄出来，就有点得不偿失了：

可以仅仅根据儿子的Hash值对儿子进行排序，由于Rabin-Karp的Hash函数是可以处理两个串连接后的Hash函数值的，在确定了顺序并且知道了各个儿子的节点数（即子串的长度），不难确定当前节点的Hash值。

换句话说，如果用c1,c2,…,cD表示当前节点v的儿子节点，s（x）表示根节点为x的子树所转化成的子串，则

，这里g（v）是某个关于v的有一定识别能力的函数，比如取节点v的儿子数，或者某个关于节点v的Hash函数均可。

而Rabin-Karp算法的Hash函数为

因此有

可见，进行一次在树上的递推，则Hash值不难算出。

问题2：

比较两棵无根树是否相同。

此时再使用最小表示的话，时间复杂度就很高了。

但是，如果合理地使用Hash，时间复杂度依然只有O（nlogn）。

具体办法如下：

对于每条边

，计算一个Hash值

，使之与所有满足

的

有关，这里

和

是两个概念，如图：

可见，这样的递推计算不会引起循环，一定可以依照某个顺序进行。

就用来表示“以a作为b的父亲节点时，b为根的子树的Hash值。

”

首先，任意选取一个节点r作为根节点，对于一个有序点对

，满足

，如果a比b离根节点近，则称

是向下的，否则是向上的。

显然，可以使用刚才问题1中给出的第二个方法在O（nlogn）时间内求出所有向下的

对应的

。

现在考虑这个根节点r。

显然所有

都是向下的，因此所有

都是已知的。

现在就是要计算各个

。

对于r的某一个儿子节点t，如图所示：

那么

可以通过r的除了t以外其他的儿子节点的Hash值计算出来。

但是如果直接这样计算，时间复杂度在最坏情况下就是O（n2）的了。

这里要用到树状递推的一个小技巧：

由于所有

都是已知的了，不妨事先对它们进行排序，然后考虑。

由于这个Hash函数本质上还是对串的Hash，不妨把r所连接的各个点按

排序，分别记作c1,c2,…,cD，记

为

所对应的那个串。

可以在c1,c2,…,cD中二分查找到t的位置k，则

可以表示成：

略去不谈（同例一），

和

在排完序后都不难在O（n）时间预处理算出。

因此，可以在O（logn）时间内算出

，因为用到了二分查找。

当一个节点v满足

已经被计算出之后，就相当于对于所有与之相邻的点i，

都是已经计算出的了。

这个情况就和刚才关于根节点r的讨论相同了，在此不再赘述。

这样，第一遍dfs可以确定所有向下的

，而第二遍dfs又可以确定所有向上的

，这样，就计算出了。

时间复杂度如何呢？

第一遍复杂度显然是O（nlogn），而第二遍的时间复杂度：

对于一个有D个儿子节点的节点，时间复杂度为O（DlogD）

一个顶点的Hash值可以定义为，以这个节点为根时整棵树的Hash值。

在所有的

计算出之后，顶点的Hash值不难计算。

最后，如果两个无根树的顶点的Hash值可以一一对应（即排序以后完全对应，或者使用一个Hash表判定），就可以认为它们是相等的，否则认为它们是不相等的。

由于顶点的Hash值就相当于把这个顶点作为根节点时得到一棵有根树，再Hash得到的结果。

可以直接用顶点的Hash值是否相同比较两个顶点是否在树里处于等价的位置上，或者可以通过顶点的一一对应得到两棵结构一样但是顶点顺序不同的无根树的顶点的对应关系。

由于变更一个顶点会导致整个树上所有节点的Hash值发生变化，因此Hash值相同也能反映出“这两个节点所属的树很可能是同一棵，或是完全一样的两棵”，这种Hash甚至可以用来判断一个森林里哪些点是处在等价的位置上的。

问题3：

比较两个有向图是否相同。

由于无向图的情况可以转化为有向图的情况考虑，这里只讨论有向图的情况。

我目前还没有找到什么非常有效的Hash的办法，但是有一个实践中没有遇到过问题的算法：

先枚举一个起始点i，所有结点的Hash值置为某个常数（不妨取1）。

然后进行迭代，每次一个节点新的Hash值计算为：

这里

然后迭代k次，计算出的

就是i点的Hash值。

其实关键就是在于fj（i）的计算和其他值不同，即可避免很多特殊情况。

有关题目：

Thelabyrinthofwells（POI1999/2000Stage2）

题目大意：

有若干个房间，最上面一个是起点，最下面一个是终点，除了最下面的房间外每个房间都是3种颜色中的一种，且有3根不同的管道通往它下面的房间。

所有的房间都可达，且所有的管道最后通往的都是最底下的房间。

但是有些节点其实本质是一样的（采取一样的走法就能经过同样颜色），问把本质一样的节点合并之后，最后最少能剩下多少点。

两个点能合并当且仅当它们后面的路的颜色完全一样，可以据此设计一个Hash函数，即Hash（x）=f（Hash（x->c1）,Hash（x->c2）,Hash（x->c3）,x->color），f是某个Hash函数。

在我的程序中，Hash函数为：

f（a,b,c,d）=（（129（129axorb）xorc）xor987654321）+d。

顺便介绍一下，为了提高程序的运行效率，可以使用一些位操作的技巧，如a*129=（ashl7）+a。

例题5等价表达式（NOIP2005）

题目大意

给定一个没有化简的整式，然后n个整式，求出这n个整式里哪些与一开始给定的多项式相等。

限制条件：

n<=26，表达式长度不超过50，整式中只出现数字,a,+,-,*,^（乘方运算）,左右括号和空格。

数字都小于10000，乘方运算中幂次都不超过10，+-*^（）都只能作运算符，且不会出现省略乘号的现象。

算法分析

常规的解法是把各个整式都展开并合并同类项，然后进行比较。

这个算法当然是可以通过比赛时的测试数据的。

但是这样的数据呢（显然这组数据是符合题目要求的）？

（a+9999）^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9

不难看出，这组数据展开以后得到的多项式根本无法存储下来，也难以表示它后面各项的系数。

面对这样的庞然大物，怎么比较两个都如此巨大的整式是否相同？

显然，即便把这个式子计算出来都是极为困难的，更不要说去比较了。

事实上，解决办法很简单：

给a带一个或几个值，根据带值计算出的结果对某个大数字取余的余数（不取余的话上面那组“巨型”数据还是解决不了）是否相等，直接判定这两个整式是否相等。

而代入一个值去求值，也可以看作是在本题应用了一个特殊的Hash函数对两个整式计算了Hash值，并通过比较Hash值来比较原式是否相等。

当然，如果a取了若干个合适，可以证明出这个算法就变成一定正确的了。

例题6GuesstheNumber（OIBHReminiscenceProgrammingContest改编）

题目大意

给定一个S（最多500000位），求N，使得NN=S。

但可能给定的S可能有一些位上的数字错了（不会出现增加或减少位数的情况），此时应输出-1。

算法分析

首先，对于比较小的S可以直接判断处理，而对于超过1010的S，我们可以确定一个可能的N（因为

在N≥10时显然大于10，不可能位数相同），剩下的工作就是判断这个N满不满足NN=S。

显然，算对数是不可取的，因为实数类型没有这么高的精度。

同理，高精度计算也是难以实现的（即使是FFT也面临着时间复杂度的挑战）联系到前面的例题，可以想到，找到一个Hash函数f（x），通过比较f（NN）和f（S）是否相同即可确定NN是否和S相等。

同时，这个f（x）还要满足，如果x=ab，则可以方便地通过f（a）和f（b）来计算得到f（x），以便可以不把NN计算出来就直接比较。

一个很简单但是很有效的Hash函数就是取余！

即，f（x）=xmodp。

如果x=ab，则

f（x）=f（a）f（b）modp。

对于原题（S和NN 最多相差一位），只要p不能被10整除，即可保证判断的准确性。

而改编之后的题目呢（S 可以修改任意位）？

取若干个p，由于S的长度限制（只有500000）位，不超过130000以内质数的乘积。

换句话说，在500000内随便取一个p，恰好能被|S-NN|整除的可能性只有大约1/4，如果多取一些，或者再加大p的范围就可以几乎肯定判断是正确的了。

【总结】

Hash函数除了做为Hash表的辅助工具，在单独使用的时候可以实现几乎肯定地判断两个数据是否相同或等价。

Hash函数的本质是对含有较大信息量的信息加以“概括”。

因此在遇到需要频繁比较两个数据是否相同的操作的问题时，不妨考虑使用Hash函数作为解题的工具。

有时使用Hash函数会牺牲一定的正确性，而且使用Hash函数的算法看上去也不够优美。

但是灵活使用Hash函数，可以化难为易，解决一些原来难以解决的问题。

也往往可以用较短的代码获得较高的效率。

尽管有所舍弃，却也有所收获；正因为有所舍弃，才会有所收获。

在选择算法的时候，总会遇到这样的矛盾，有失必有得，有得也必有失，选择恰当的适合题目也适合自己思维习惯的算法才是最好的。

【参考文献】

刘汝佳黄亮《算法艺术与信息学竞赛》清华大学出版社

陈启峰《NEWLCP》2006年国家集训队作业

《数据结构》清华大学出版社