注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

3097 3098 3099: Hash Killer I II III  

2013-03-29 11:32:09|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目自己看吧~


其实我觉得用纯文字写这篇题解写起来压力大看起来也压力大啊囧……
这几题的坑爹之处在于base是根据心情定的……
先扯下闲话说下spj的事吧~
spj分为两部分……
一个是用后缀数组跑你输出出来的数据,得到正确答案。(这部分是hzhwcmhf帮忙写的,orz)
一个是找一堆base跑你输出出来的数据,得到一堆答案。
然后只有有一个答案跟正确答案相同,你就WA了。
而且Hash Killer III的spj更加变态,还取了好多个mod。
鸣谢hzhwcmhf,两人合作所以三道题一下午就出完了。

【Hash Killer I的解法】
太神了orz。

爆u64相当于对2^64取模。
如果base是偶数的话就很好卡了,aaa......a,baaa......a,a有好多好多个,这两个字符串的hash值是相同的。

如果base是奇数的话,现在只考虑a、b两个字母。
a \ b表示a能整除b。(orz 具体数学)
设数学上的函数not(S)表示把字符串S中每个位置的'a'变成'b',把'b'变成'a'后形成的字符串。比如not("ababaa") = "bababb"
strA . strB代表字符串串联。如"娃" . "哈哈" = "娃哈哈"
|str|表示字符串str的长度。
设字符串序列{orzstr[i]},orzstr[1] = "a", orzstr[i] = orzstr[i - 1] . not(orzstr[i - 1])
那么|orzstr[i]| = |orzstr[i - 1]| * 2。显然这是等比数列,得到:|orzstr[i]| = |orzstr[1]| . 2 ^ (i - 1) = 2 ^ (i - 1)
设hash(str)为str的哈希值。
则:
hash(orzstr[i]) = hash(orzstr[i - 1]) * base ^ |not(orzstr[i - 1])| + hash(not(orzstr[i - 1]))
                       = hash(orzstr[i - 1]) * base ^ (2 ^ (i - 2)) + hash(not(orzstr[i - 1]))
hash(not(orzstr[i])) = hash(not(orzstr[i - 1])) * base ^ (2 ^ (i - 2)) + hash(orzstr[i - 1])
两式相减:
   hash(orzstr[i]) - hash(not(orzstr[i]))
= (hash(orzstr[i - 1]) * base ^ (2 ^ (i - 2)) + hash(not(orzstr[i - 1]))) - (hash(not(orzstr[i - 1])) * base ^ (2 ^ (i - 2)) + hash(orzstr[i - 1]))
= (hash(orzstr[i - 1]) - hash(not(orzstr[i - 1]))) * (base ^ (2 ^ (i - 2)) - 1)
这让我们发现,hash(orzstr[i]) - hash(not(orzstr[i]))似乎是个神奇的东西。而我们的目的实际上是要找两个字符串strA, strB使得
hash(strA) % 2^64 = hash(strB) % 2^64
相当与
2^64 \ hash(strA) - hash(strB)
设数列{f[i]},f[i] = hash(orzstr[i]) - hash(not(orzstr[i]))
这样就有:
f[i] = f[i - 1] * (base ^ (2 ^ (i - 2)) - 1)
还是有点不爽啊……我们再设数列{g[i]},g[i] = base ^ (2 ^ (i - 1)) - 1
于是能写成:
f[i] = f[i - 1] * g[i - 1]
则f[i] = f[1] * g[1] * g[2] * ... * g[i - 1]
然后发现一个神奇的事情?
base是奇数,则base的任意正整数次方也一定是奇数。所以对于任意的i必有g[i]为偶数,所以2 ^ (i - 1) \ f[i]
问题是不是结束了呢……发现没有……这样的话我们要使2 ^ 64 \ f[i],至少得让i = 65……然后发现|orzstr[65]|是个天文数字。
发现我们刚才那样分析太坑爹了……
i > 1时有:
g[i] = base ^ (2 ^ (i - 1)) - 1 = (base ^ (2 ^ (i - 2)) - 1) * (base ^ (2 ^ (i - 2)) + 1) = g[i - 1] * 一个偶数
而g[1]显然是偶数吧……
那么4 \ g[2],8 \ g[3]...
也就是说2 ^ i \ g[i]
所以f[i] 实际上有:
(2 ^ 1) * (2 ^ 2) * (2 ^ 3) * ... * (2 ^ (i - 1)) \ f[i]
2 ^ (i * (i - 1) / 2) \ f[i]
当i取12时,就有66个2了哟!
这就是卡base为奇数时的方法。orzstr[12]和not(orzstr[12])即为所求。

可是spj里既选了奇数又选了偶数……
显然还是很好办吧……

#include <iostream>
#include <cstdio>
using namespace std;

const int MaxN = 100000;

int main()
{
int n, l;
static char s[MaxN + 1];

n = 1;
s[0] = 'a';
for (int i = 0; i < 12; i++)
{
for (int j = 0; j < n; j++)
s[j + n] = s[j] == 'a' ? 'b' : 'a';
n <<= 1;
}

l = n >> 1;

s[n++] = 'a';
for (int i = 1; i < l; i++)
s[n++] = 'a';
s[n++] = 'b';
for (int i = 1; i < l; i++)
s[n++] = 'a';

cout << n << " " << l << endl;
s[n] = '\0';
printf("%s\n", s);

return 0;
}


【Hash Killer II的解法】
首先请拿出你的《算法导论》翻到第五章看生日悖论。
看完了么?
那你一定已经会做了……
说实话这题也太水了点吧……

取模的数mod约为10^9
只要大约sqrt(mod)个字符串,很大几率有两个字符串哈希值相同。
况且字符串长度n最大是10^5,想办法构造出来S使得n - L + 1个长度为L的子串互不相同。
L取小一点,这样就有接近10^5个字符串,大于sqrt(mod)了吧~这要是没能卡掉hash请自行购买福利彩票。
当然了,L不能太小,一定要让哈希值不取模时超过mod,不然这个hash就是正确的囧,永远hack不掉。
我以为构造出来S使得n - L + 1个长度为L的子串互不相同是很困难的,结果发现裸随机就行了囧……

这就是为啥hash有时虽然是模了一个素数,但是还是WA了。
sqrt(状态数)太小是能被生日攻击干掉的。
当然要是问题不是“有多少个不同的?”而是“这两个相不相同?”,生日攻击就无效了。

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

const int MaxN = 100000;

int main()
{
int n, l;
static char s[MaxN + 1];

n = MaxN, l = 13;
for (int i = 0; i < n; i++)
s[i] = rand() % 26 + 'a';
s[n] = '\0';

cout << n << " " << l << endl;
printf("%s\n", s);

return 0;
}


【Hash Killer III的解法】
这题我不会做。
前两题是引子,这题是我的目的 T_T
这题生日攻击都没法做。
哪位神犇A掉了此题,不管用的是啥方法一定要告诉我啊啊啊 T_T
  评论这张
 
阅读(3231)| 评论(6)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017