a. 利用可扩散列的算法实现字谜程序。(字谜游戏描述:输入一些字母和单词的二维数组组成。目标是要找出字谜中的单词,这些单词可能是水平,垂直或沿对角线以任何方向放置的)
b. 通过存储每一个单词W以及W的所有前缀,我们可以大大加快运行速度(如果w的一个前缀刚好是词典中的一个单词,那么就把它作为实际的单词来储存。)虽然这看起来极大地增加了散列表的大小,但实际上并不是,因为许多单词有相同的前缀。当以某个特定的方向执行一次扫描的时候,如果被查到的单词作为前缀不在散列表中,那么在这个方向上的扫描可以及早终止。利用这种思想编写一个改进的程序来解决字谜游戏问题
c. 如果我们愿意牺牲散列表ADT的严肃性,那么我们可以在(b)部分使程序加速:例如,如果我们刚刚计算出‘excel’的散列函数,那么我们就不必再从头开始计算‘excel’的散列函数。调整散列函数使得它能够利用前面的计算。
d. 把使用前缀的想法结合到对分查找算法中。比较哪个算法那更快?
