HASH GAME - Online Skill Game GET 300

　　下的 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(kNM)。 k 维时的 Hash 函数：

　　如果没有最后的 mod q 操作，那么这个 Hash 函数可以理解成一个进制转换，当每次的 p 都取得比当时的字符集还要大的时候，只要 Hash 值不同就一定能确定内容不同。但是事 实上计算出来的 Hash 值就会大到使这个算法没有意义的程度（比较这个“Hash 值”的速度 不会比直接比较更快） ，因此取余是必须的。 一个理想情况下的 Hash 函数，如果能产生 S 种不同的值，那么对两个不一样的子数组 算出一样的值的可能性就只有 1/S。 我们的 Hash 函数当然未必能达到理想情况， 但是由 “1/S” 这个式子不难想到，加大 S 就能有效地减少判错的可能性。并且还能得出另一个结论：如果 一个 Hash 函数的精确程度不够，只需要再计算一个与之不同的 Hash 函数，就可以有效地 提高正确率！当然，在本题中，时间复杂度已经近似于（因为毕竟这个 Hash 函数不是理想 的 Hash 函数)O(kNN*(1/S)*M)了。 只要大小不比 N/k 小， S 后一项就不是时间复杂度的瓶颈 了，也没有必要在这方面下太大功夫。反而，如果计算多个 Hash 函数，会显著增加算法的 常数。 关于 p 和 q 的取值，由于可以理解成一个 p 进制的转换，再对 q 取余，应当在范围允许 的情况下尽量避免冲突，建议： 1、 p 不宜过小，不然很容易出错。 2、 q 可以取一个质数，然后 p 选取一个能使对于所有 1 至 p-2 的 i，pi mod q≠1。 这个 Hash 函数不但可以这样滚动计算，也可以采用分段，分块，线段树等办法计算和 维护，具体的一些办法可以参见后面的一些例题。

　　换个角度，如果不考虑 mod q，这个函数就是把字符串看作一个 p 进制数求出的值，这 样，Xi1 就是 Xi “左移”一位，然后去掉最前面一位，再加上右面新进来的一位得到的。 因此上面的递推公式也是显然的。 有了这个递推公式，不难在线性时间内求出 X 的所有长度为 M 的子串的 Hash 值。 现在把问题扩展到高维的情况。不难发现要计算的 Hash 值的个数仍然不超过 N 个，可 见，只要有合适的递推方法，仍然可以在线性时间内求出所有子矩阵的 Hash 值。事实上， 一个 M1 行，M2 列的子矩阵可以被看作是 M2 个“竖条”组成的一个串。我们可以先把每个 长度为 M1 的“竖条”计算出一个 Hash 值，然后再计算二维情况的 Hash 值。 需要注意的一点是，在计算一维的 Hash 值（ “竖条”的 Hash 值）和计算二维的 Hash 值时使用的 b 值不能一样，不然不难想到下面反例： a a b a a b a a

　　本题常见的算法是多维情况的 KMP，先算 1 维时的匹配情况，然后处理 2 维，3 维…… 直到 N 维时的情况。时间复杂度为 O(k*(NM))。但是它难以理解和记忆，也不容易在比赛 中的短短几个小时完成和写对。 朴素的解法相对易于实现，但是使朴素算法很容易想到，而且针对数据又很容易制作， 因此只有在完全没有思路的时候才值得一试。 有没有第三种选择呢？答案是肯定的。 朴素的解法相当于枚举了每个起点 （起点数量显 然不会超过 N）并加以判断，然而判断两个子数组是否相同的时间复杂度高达 O(M)，这就 是导致朴素算法在遇到针对数据的情况下很慢的原因。 能不能在比较两个子数组之前先快速 地排除一些明显不可能的情况呢？由于很容易构造出仅有一个字符不同的数据， 不管采用什

　　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 的经验，在面对本题的时候不难想到，二分查找正方形的边长，然后使用一 个 Hash 表来判断该边长是否可行。Hash 函数与例题 1 的二维情况一致。时间复杂度是 O(NMlog(N*M))的。 但是不幸的是，本题时间限制很严，这样做的程序依然会超时。最后在使用一个看上去 有点冒险的改动之后，终于通过了本题：直接检查是否产生了相同的 Hash 函数，如果存在 相同的 Hash 函数，则认为该边长可行，否则即认为它不可行。 这道题目就这样通过了， 但是这样的改动是不是太冒险了一点呢？事实上， 两个子正方 形的内容不同而 Hash 值相同的可能性很小。所以，一般情况下我们可以认为，如果 Hash 值相同，则原内容相同。 这里还有一个问题：Hash 表存放了什么？如果存放的是 Bool 而不使用位压缩，则似乎 浪费了不少空间，而且 Hash 表不可能开到很大，因此两个不同的内容 Hash 到同一个位置 还是有可能的，简单地比较“这个位置是否被 Hash 到”仍然不算保险，毕竟，一次查询有 100 万分之一的可能性出错的线 万次查询出错概率就很可观了。这里介绍的一个小技 巧是计算两个 Hash 值，一个用于确定 Hash 表中的位置，另一个则用于比较。这样，只有 如果在 Hash 表的某个地址开始查找找到了一个 Hash 值与自己的 Hash 值一样的元素，才认 为自己在 Hash 表中出现过。

　　么顺序比较都会消耗大量的时间。 Hash 函数在这里派上了用场。我们可以对每个尺寸与模式数组一样的子数组计算一个 Hash 值。显然，只有当某个子数组的 Hash 值与模式数组的 Hash 值一样，它们才值得比较。 多维的 KMP 要从 1 维的情况开始考虑，并推广至高维。那么这种计算 Hash 函数的匹 配算法我们也可以先考虑一维的情况——就是 Rabin-Karp 算法。 对于一个字符串 S，可以使用这个函数求出其 Hash 值：

　　它们并不相同，但是 Hash 的结果肯定一样。这就违背了使用 Hash 的初衷。因此，在 第一维的计算和第二维的计算中要使用不同的 p 值。 二维情况时，求出所有长度为 M1 的“竖条”所需要花费的时间是 O(N)的，然后把这些 竖条的 Hash 值看作“字母”计算横向的 Hash 值（即各个子矩阵的 Hash 值） ，所花费的时 间也是 O(N)的。总时间复杂度仍然是 O(N)的。 二维情况的 Hash 函数为（len1(S)和 len2(S)分别表示 S 在两个维度上的大小） ：