从Hash Killer I、II、III论字符串哈希

首先,Hash Killer I、II、III是BZOJ上面三道很经典的字符串哈希破解题。当时关于II,本人还琢磨了好久,但一直不明白为啥别人AC的代码都才0.3kb左右,直到CYG神犇说可以直接随机水过去,遂恍然大悟。。。

于是,本人今天也做了下实验——假设现在有一个字符串题:输入N,接下来N行输入N个长度一样的由大写字母组成的字符串,求一共有多少种不同的字符串。此题有些类似于Hash Killer上面的原题。首先分析此题本身,两种常规办法:1.建立一棵字典树,然后可以相当方便快捷的判重,对于字符串长度均为M的数据,复杂度O(NM)  2.字符串哈希,选取一对质数pa和pb,哈希值为Sigma((ord(s1[i])-64)*pa^i) mod pb,然后通过哈希值排个序完事

接下来开始——字典树肯定能保证正确这个毫无疑问,但是更加毫无疑问的是哈希是相当容易被卡掉的(HansBug:尤其像Hash Killer II这样素数的神选取我也是醉了),但更加更加毫无疑问的是双取模哈希似乎还比较小强,于是我就此展开实验

1.写出一个数据生成器,负责随机生成N个长度为M的大写字母字符串,然后立刻用Trie树求出答案作为标准输出数据

 1 type
 2         point=^node;
 3         node=record
 4                 ex:longint;
 5                 next:array['A'..'Z'] of point;
 6         end;
 7 var
 8         i,j,k,l,m,n,ans:longint;
 9         head:point;
10         s1,s2:ansistring;
11 function getpoint:point;inline;
12         var p:point;c1:char;
13         begin
14                 new(p);p^.ex:=0;
15                 for c1:='A' to 'Z' do p^.next[c1]:=nil;
16                 exit(p);
17         end;
18 function check(s1:ansistring):longint;inline;
19         var i:longint;p:point;
20         begin
21                 p:=head;
22                 for i:=1 to length(s1) do
23                         begin
24                                 if p^.next[s1[i]]=nil then
25                                         p^.next[s1[i]]:=getpoint;
26                                 p:=p^.next[s1[i]];
27                         end;
28                 if p^.ex=0 then
29                         begin
30                                 inc(ans);
31                                 p^.ex:=ans;
32                         end;
33                 exit(p^.ex);
34         end;
35 begin
36         readln(n,m);
37         head:=getpoint;ans:=0;
38         RANDOMIZE;
39         assign(output,'hs.in');
40         rewrite(output);
41         writeln(n);
42         for i:=1 to n do
43                 begin
44                         s1:='';
45                         for j:=1 to m do s1:=s1+chr(random(26)+65);
46                         writeln(s1);
47                         check(s1);
48                 end;
49         close(output);
50         assign(output,'hss.out');
51         rewrite(output);
52         writeln(ans);
53         close(output);
54 end.

2.接下来,开始写哈希,也不难,而且代码貌似还略短(这里面两个素数采用互换使用的模式,本程序是双取模的哈希,如果需要改成单值哈希的话直接把第50行去掉即可)

 1 const pa=314159;pb=951413;
 2 var
 3    i,j,k,l,m,n:longint;
 4    ap,bp:array[0..100000] of int64;
 5    a:array[0..200000,1..2] of int64;
 6    a1,a2,a3,a4:int64;
 7    s1,s2:ansistring;
 8 function fc(a1,a2,a3,a4:int64):longint;inline;
 9          begin
10               if a1<>a3 then
11                  if a1>a3 then exit(1) else exit(-1)
12               else
13                   if a2<>a4 then
14                      if a2>a4 then exit(1) else exit(-1)
15                   else exit(0);
16          end;
17 procedure sort(l,r:longint);
18           var i,j:longint;x,y,z:int64;
19           begin
20                i:=l;j:=r;x:=a[(l+r) div 2,1];y:=a[(l+r) div 2,2];
21                repeat
22                      while fc(a[i,1],a[i,2],x,y)=-1 do inc(i);
23                      while fc(x,y,a[J,1],a[J,2])=-1 do dec(j);
24                      if i<=j then
25                         begin
26                              z:=a[i,1];a[i,1]:=a[j,1];a[j,1]:=z;
27                              z:=a[i,2];a[i,2]:=a[j,2];a[j,2]:=z;
28                              inc(i);dec(j);
29                         end;
30                until i>j;
31                if i<r then sort(i,r);
32                if l<j then sort(l,j);
33           end;
34 
35 begin
36      ap[0]:=1;bp[0]:=1;
37      for i:=1 to 100000 do
38          begin
39               ap[i]:=(ap[i-1]*pa) mod pb;
40               bp[i]:=(bp[i-1]*pb) mod pa;
41          end;
42      readln(n);
43      for i:=1 to n do
44          begin
45               readln(s1);
46               a[i,1]:=0;a[i,2]:=0;
47               for j:=1 to length(s1) do
48                   begin
49                        a[i,1]:=(a[i,1]+ap[j]*(ord(s1[j])-64)) mod pb;
50                        a[i,2]:=(a[i,2]+bp[j]*(ord(s1[j])-64)) mod pa;  //删除此行即可改为单值哈希
51                   end;
52          end;
53      sort(1,n);m:=0;
54      a[0,1]:=-maxlongint;
55      for i:=1 to n do if fc(a[i-1,1],a[i-1,2],a[i,1],a[i,2])<>0 then inc(m);
56      writeln(m);
57      readln;
58 end.
59                       

于是开始愉快的用bat来对拍:

1.当N=100000 M=3时,很令人吃惊——单双值的哈希都问题不大(随机跑了403组数据均全部通过)

2.当N=100000 M=100是,果不其然——单值的哈希成功而华丽的实现了0%的命中率,而双值的哈希依然100%(HansBug:实测6001组数据,跑了快两小时有木有啊啊啊啊 wnjxyk:What Ghost? HansBug:我家电脑渣不解释^_^)

(HansBug:呵呵哒BZOJ3098这题我居然上来就WA了,现在看来这究竟是什么样的神人品啊)

结果已经了然,而且从bat上运行的时间来看,当N=100000 M=100时,哈希的速度比trie树看样子明显快——估计是虽然trie树可以达到O(NM),但是假如需要新建大量的点的话,那样势必相当费时,多半慢在这上面了,而哈希就是该怎么玩怎么玩——更重要的是——哈希,绝对不等同于非得开一个巨大的数组瞎搞,比如这个例子中直接排个序就完事啦。更重要的是双值哈希的稳定性还是相当不错滴!!!^_^

后记:以前我曾经一度认为hash算法一定就是必然伴随着一个硕大的数组(HansBug:搞不好还MLE有木有TT  bx2k:那是必然),其实它的灵活性远远超出了我的预想,今天也算是大长了见识;还有祝愿BZOJ3099(Hash Killer III)永远不要有人AC!!!否则那就基本意味着哈希算法的终结了TT

附:对拍用的bat模板,纯手写的哦,如有雷同绝无可能么么哒

 1 @echo off
 2 set /a s=0
 3 :1
 4 set /a s=s+1
 5 echo Test %s%
 6 rem 此处两个数分别代表N和M,手动修改下即可
 7 echo 10000 100|hs.exe
 8 copy hs.in hash\hs%s%.in >nul
 9 copy hsS.out hash\hs%s%.out >nul
10 echo.|time
11 type hash\hs%s%.in|hash.exe >hash\hs%s%.ou
12 echo.|time
13 fc hash\hs%s%.ou hash\hs%s%.out >hash\res%s%.txt
14 fc hash\hs%s%.ou hash\hs%s%.out
15 goto 1

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

BZOJ 3670: [Noi2014]动物园【KMP变形 】

3670: [Noi2014]动物园 Time Limit: 10 Sec  Memory Limit: 512 MB Submit: 2738  Solve...

36470
来自专栏我杨某人的青春满是悔恨

Swift API 设计指南(下)

一般来说,默认参数比方法族(method families)更可取,因为它减轻了 API 使用者的认知负担。

8420
来自专栏CSDN技术头条

为什么我坚持使用 JavaScript 函数声明

时光溯回到上世纪 90 年代晚期,在初次接触 JavaScript 时,老师教我们使用函数声明写下Hello World,它看上去是这样的······ fun...

22180
来自专栏Python入门

十五道Python小案例,学会这些,Python基础已过关!

分析:可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去 掉不满足条件的排列。

58240
来自专栏ACM小冰成长之路

51Nod-1645-中位数变换

ACM模版 描述 ? 题解 这个题很明显是找规律的问题,直接暴力肯定会超时……虽然我也是暴力也两发才反应过来……平时做题总是抱着侥幸心理,比赛时却总是胆小如鼠…...

23170
来自专栏数据结构与算法

P3818 小A和uim之大逃离 II

题目背景 话说上回……还是参见 https://www.luogu.org/problem/show?pid=1373 吧 小a和uim再次来到雨林中探险。突然...

32070
来自专栏Danny的专栏

面向对象三大特征

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

23220
来自专栏chenjx85的技术专栏

leetcode-258-Add Digits

22140
来自专栏编舟记

函数式编程简介

1900年,Hilbert 提出了数学界悬而未决的10大问题,后续陆续添加成了23个问题,被称为著名的 Hilbert 23 Problem。针对其中第2个决定...

23140
来自专栏前端布道

JavaScript 浮点数陷阱及解法

众所周知,JavaScript 浮点数运算时经常遇到会 0.000000001 和 0.999999999 这样奇怪的结果,如 0.1+0.2=0.300000...

39730

扫码关注云+社区

领取腾讯云代金券