《1杨弋《Hash在信息学竞赛中的一类应用》》由会员分享，可在线阅读，更多相关《1杨弋《Hash在信息学竞赛中的一类应用》（13页珍藏版）》请在金锄头文库上搜索。
1、Hash在信息学竞赛中的一类应用【正文】Hash表作为一种高效的数据结构，有着广泛的应用。如果Hash函数设计合理，理想情 况下每次查询的时间花费仅仅为O(h/r)，即和Hash表容量与剩余容量的比值成正比。只要 Hash表容量达到实际使用量的大约1.5倍以上，查询花费的时间基本就可以认为恒为0(1)。对于一个Hash表，一个好的Hash函数是尤其重要的，因为它能使Hash表保证效率。 一个好的Hash函数最显而易见的特征是，能使不相同的东西经过Hash之后只有很小的几 率相同。这样能避免过多冲突的产生。Hash表离不开Hash函数，但是反过来呢？有的时候，Hash函数却是可以离开Hash表
2、的。一个常见的例子就是著名的MD5算法，它是一个Hash函数，但是它的用途往往是对 信息进行加密，以验证信息的正确性。换句话说，我们事实上是通过直接比较MD5算出的 结果是否相同以推断原文内容是否一致。除了 MD5,常用的CRC32校验码和SHA-1算法 也是基于类似的想法而产生的。那么，信息学竞赛中，这样的算法有没有用武之地呢？本文要讨论的，就是这一类以判重或判等价为目标的Hash函数。让我们来看看例题1。例题1多维匹配题目大意在一个串中求另一个串第一次出现的位置，很简单，KMP即可。扩展到二维情况，就 是求在一个矩阵中求另一个矩阵第一次出现的位置。而如果扩展到k维的情况，又该怎么做 呢？待
3、匹配数组X各维的尺寸为N1，N2，Nk，模式数组Y各维的尺寸为MM2， Mk。记 N=NN2Nk，M=MM2Mk。保证 kW10，N.M尸而 N 和 M 都不超过 500000。算法分析本题常见的算法是多维情况的KMP，先算1维时的匹配情况，然后处理2维，3维 直到N维时的情况。时间复杂度为0(k*(N+M)。但是它难以理解和记忆，也不容易在比赛 中的短短几个小时完成和写对。朴素的解法相对易于实现，但是使朴素算法很容易想到，而且针对数据又很容易制作， 因此只有在完全没有思路的时候才值得一试。有没有第三种选择呢？答案是肯定的。朴素的解法相当于枚举了每个起点(起点数量显 然不会超过N)并加以判断，
4、然而判断两个子数组是否相同的时间复杂度高达O(M)，这就 是导致朴素算法在遇到针对数据的情况下很慢的原因。能不能在比较两个子数组之前先快速 地排除一些明显不可能的情况呢？由于很容易构造出仅有一个字符不同的数据，不管采用什么顺序比较都会消耗大量的时间。Hash函数在这里派上了用场。我们可以对每个尺寸与模式数组一样的子数组计算一个 Hash值。显然，只有当某个子数组的Hash值与模式数组的Hash值一样，它们才值得比较。多维的KMP要从1维的情况开始考虑，并推广至高维。那么这种计算Hash函数的匹 配算法我们也可以先考虑一维的情况就是Rabin-Karp算法。对于一个字符串S，可以使用这个函数求出
5、其Hash值：f (S) = Wsipien(s)-i mod qi=1那么，模式串7的Hash值就可以轻松地求出。记待匹配串X从第i个字符开始的长度 为M的子串为S,，则不难发现f(Si+1 )和f(S)的关系：mod qmod qf (Sj)= 方(X j pi+M -1- j ) j=if (Si+1) =S ( X j pi+M - j )j=i+1mod qp -无(X jpi+m-1-j) + X i + M 一 pM X i pf (S ) + X i + M 一 pMX i mod qi换个角度，如果不考虑mod q，这个函数就是把字符串看作一个p进制数求出的值，这 样，Xi+
6、1就是X, “左移”一位，然后去掉最前面一位，再加上右面新进来的一位得到的。 因此上面的递推公式也是显然的。有了这个递推公式，不难在线性时间内求出X的所有长度为M的子串的Hash值。现在把问题扩展到高维的情况。不难发现要计算的Hash值的个数仍然不超过N个，可 见，只要有合适的递推方法，仍然可以在线性时间内求出所有子矩阵的Hash值。事实上， 一个M行，M2列的子矩阵可以被看作是M2个“竖条”组成的一个串。我们可以先把每个 长度为M的“竖条”计算出一个Hash值，然后再计算二维情况的Hash值。需要注意的一点是，在计算一维的Hash值(“竖条”的Hash值)和计算二维的Hash值时使用的b值不
7、能一样，不然不难想到下面反例：a | a |它们并不相同，但是Hash的结果肯定一样。这就违背了使用Hash的初衷。因此，在 第一维的计算和第二维的计算中要使用不同的p值。二维情况时，求出所有长度为M1的“竖条”所需要花费的时间是O(N)的，然后把这些 竖条的Hash值看作“字母”计算横向的Hash值(即各个子矩阵的Hash值)，所花费的时 间也是O(N)的。总时间复杂度仍然是O(N)的。二维情况的Hash函数为(jn1(S )和len2(S )分别表示在两个维度上的大小): f (s )=len1(S) 2(，pien1(S)-i1 plen1(S)-i2Si , i y mod q2i =
8、1i =1121 212类似地，记待匹配矩阵X从第很亍，第/列为左上角的M行，M列的子矩阵为X1212七，勺我们有递推式：f G )= i1+ M1-1 i2+ M2-1 Qi； + m 1 -1-j1 pi2 + m2 -1-j2 X j , j ) mod q2 / e )寸=s p=i2 u 21 2)f J= i1+ M1-1 i2+ M2 pi1 + m 1 -1-j； pi2 + m2 -j2 X j , j y mod q2 2 +1j = ij = i +1；/212、/、=D Lii + M1 -1 LL2 + M2 -1 pi + M -1- j pi + M -1- j
9、X J J 4 Lii + M1 -1 pi + M -1-j X J i + M p 1122 p 11 J1 p 22,11 p 11,2 j i12=，21)1 2Ji =i111 22-pM ii+ M1-1 pi + m -1- j X j, i mod q2j1 = i111 2=n fX+乂 + m -ni + m ijX ii + M -nm乂 + M-i 7i+ mijX i i k mod Qp j11 1 p1 j； /星 l J ,j pm 21 1 p1 j； /星 |_ / , c mu5 q2 2 i；,i2j； =i；11 222j； =i；11 2式中 1 +
10、叩。+ M1 -1-jX j ,i + M )和 2 +叩。+ M1 -1-jX j ,i )都是一维情况, _，-11 22, _i 11 2jL1j1 i下的Hash值，即预先计算出的“竖条”的Hash值。nrr女扩展到k维情况，则不难想到，先算出所有尺寸为MXM2XXMk-1的子数组的Hash 值，再使用类似上面的办法把这些尺寸为MXM2XXMk-1的子数组的Hash值看作一个个 字符而使用Rabin-Karp的Hash函数计算出各个尺寸为MXMXXMk的子数组的Hash 值。可见，需要k轮计算就可以算出所有尺寸为M1XM2XXMk的子数组的Hash值，时 间复杂度为O(kN+M)。k维
11、时的Hash函数：f X )= i1+M1-1 i2+M2-1ik +Mk-1 Ci+M1-1-/ pi +m -1-j pik+m -1-j X j, j , , j ) mod qJ.11 x222L k k k J J ，J ，J qJ.k ii,j =ij =ij =i12k1 2 k1 2 kj1 i1j2 2Jk k类似地可以推出递推式 )f X)-p - f X )k L i，匕 +1 w_ 2 k 二,i，,iw,/12 k12 k+ Zi1+M1-1 2 +M2-1 k-1+Mk-1T P1+M1*1 p +M2-1-2 PL+Mk/-kXj ,j ,j , i + M )j
12、1 j2夺jk寸1 /2k-11 2k-1 k )pM 乙 1+M1-1 乙2 +M2-1乙k-1+Mk-1-1 pi +m-1-j dl +M-1-j ，1+m, ,-1-j, X j j , j i v mod q ir k 1 12 2k 1 k 1 r 1 1 1f 2 2 J2 F k-1 k-1 k，*ij ，J ， ，J ,5 qk i =ii =ii =i12k-112k-1kJrj2 i2Jk-1 ik-1如果没有最后的mod q操作，那么这个Hash函数可以理解成一个进制转换，当每次的 P都取得比当时的字符集还要大的时候，只要Hash值不同就一定能确定内容不同。但是事 实上
13、计算出来的Hash值就会大到使这个算法没有意义的程度（比较这个Hash值”的速度 不会比直接比较更快），因此取余是必须的。一个理想情况下的Hash函数，如果能产生S种不同的值，那么对两个不一样的子数组 算出一样的值的可能性就只有1/S。我们的Hash函数当然未必能达到理想情况，但是由“1/S” 这个式子不难想到，加大S就能有效地减少判错的可能性。并且还能得出另一个结论：如果 一个Hash函数的精确程度不够，只需要再计算一个与之不同的Hash函数，就可以有效地 提高正确率！当然，在本题中，时间复杂度已经近似于（因为毕竟这个Hash函数不是理想 的Hash函数）O（kN+N*（1/S）*M）了。S
14、只要大小不比N/k小，后一项就不是时间复杂度的瓶颈 了，也没有必要在这方面下太大功夫。反而，如果计算多个Hash函数，会显著增加算法的 常数。关于p和q的取值，由于可以理解成一个p进制的转换，再对q取余，应当在范围允许 的情况下尽量避免冲突，建议：1、p不宜过小，不然很容易出错。2、q可以取一个质数，然后p选取一个能使对于所有1至p-2的i，pi mod q尹1。这个Hash函数不但可以这样滚动计算，也可以采用分段，分块，线段树等办法计算和 维护，具体的一些办法可以参见后面的一些例题。例题 2 Equal squares (Ural I486)题目大意在一个NXM的字符矩阵中找到两个相同的子正
15、方形矩阵(可以相交)，并使找到的两 个子正方形矩阵的边长尽量大。算法分析有了例题1的经验，在面对本题的时候不难想到，二分查找正方形的边长，然后使用一 个Hash表来判断该边长是否可行。Hash函数与例题1的二维情况一致。时间复杂度是 O(NMlog(N*M)的。但是不幸的是，本题时间限制很严，这样做的程序依然会超时。最后在使用一个看上去 有点冒险的改动之后，终于通过了本题：直接检查是否产生了相同的Hash函数，如果存在 相同的Hash函数，则认为该边长可行，否则即认为它不可行。这道题目就这样通过了，但是这样的改动是不是太冒险了一点呢？事实上，两个子正方 形的内容不同而Hash值相同的可能性很小。所以，一般情况下我们可以认为，如果Hash 值相同，则原内容相同。这里
