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

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;
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
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
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;
43      for i:=1 to n do
44          begin
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);
58 end.
59                       ```

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

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

（HansBug：呵呵哒BZOJ3098这题我居然上来就WA了，现在看来这究竟是什么样的神人品啊）

``` 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```

251 篇文章37 人订阅

0 条评论

## 相关文章

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

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

36470

8420

22180

58240

### 51Nod-1645-中位数变换

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

23170

32070

23220

22140

### 函数式编程简介

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

23140

39730