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 各维的尺寸为 N
1
,
N
2
,…,N
k
,模式数组 Y 各维的尺寸为 M
1
,M
2
,…,M
k
。记 N=N
1
N
2
…
N
k
,M=M
1
M
2
…M
k
。保证 k≤10,N
i
≥
M
i
,而 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 值:
评论0