字符串hash

课件：字符串hash

blue  

字符串HASH  

字典匹配  

给定一篇文章和一个词典。  

询问文章中出现了多少个词典中有的单词。  

这题一万种做法……  

HASH IT!  

莫名其妙  

等比数列HASH  

等比数列HASH  

等比数列hash是什么样子呢？  

hash[i]=hash[i-1]*233+str[i]  

然后hash[n]就表示字符串的hash结果。  

用unsigned long long来存hash结果。  

不需要取模，因为会自然溢出。  

或者用别的什么数据结构存。  

扩展  

这么神，你怕不怕  

字符串匹配  

字符串匹配  

TRIE  

如何用Trie来做这个事情？  

优化路径。  

HASH IT!  

COGS [月考]  

简单HASH  

月考  

有人在月考的时候作弊。学校广播把这个人D了一番。  

这个人有一些狐朋狗友。他特别不希望这些小伙伴听到广播。  

给定听到广播的人的名单和他的朋友的名单，输出哪些人听到  

了广播。  

>>>题目来源：COGS  

暴力排序  

基数排序  

TRIE  

HASH IT!  

永恒的话题……  

避免冲突  

冲突  

避免冲突  

考虑如何避免冲突。  

有一个办法：如果hash值产生冲突，则将hash乘以某个数，直  

到没有冲突为止再插入。  

另有一个本质相同的方法，即“拉链法”。在hash数组上挂链  

表，如果产生冲突则把原值挂在链表上。  

奇技淫巧  

完全避免  

我们现在也有办法完全避免冲突。  

用hash树或Trie。  

为什么不直接写Trie，而是先去hash然后避免hash冲突？  

因为有的时候，hash比Trie更有用！  

构造优秀的hash函数  

高级HASH  

同伙  

>>>题目来源：脑补  

暴力  

HASH IT!  

继续优化  

好神的题  

思考题  

阅读  

回答语文的阅读题,最重要的是什么?——当然是语言的的流畅性。但是  

际实上,将部分字文调换序顺并不会响影阅读,这一点应该是众周所知。  

批改阅读题的套路,当然就是按点给分。对于标准答案中出现的某个短语,  

如果在考生的答案中出现,那么就认为考生获得了这个短语的得分。——  

注意,将部分字文调换序顺并不会响影阅读,所以即使这个短语中，各个  

字的位置颠倒,同样也算得分 。例如,标答中包含短语“sol 大傻叉”,  

而考生回答“大傻叉 sol”,甚至“傻叉 ols 大”则同样得分。  

那么,你得赶快批改出这道题到底得了多少分——注意, 即使一个短语出  

现多次,也只算一次分。  

>>>题目来源：SOLOI Round4 T3  

出题人：不愿透露姓名的朋友，htwc1htwc@163.com  

TRIE  

有什么想法吗？  

其实我也不会，233  

扫描  

葱娘说得好，想完暴力就去想骗分。  

对于60%的数据，每条得分短语的长度都相同，而且字符集大  

小为100.  

由于这个性质，我们就扫描主串，记录元素出现的次数。  

a [a b c d a] c c b d  

a:2 b:1 c:1 d:1  

a a [b c d a c] c b d  

a:1 b:1 c:2 d:1  

向右扫描  

扩展  

考虑扩展之前的算法。前面的算法有两个瓶颈：  

1)无法应对得分短语长度不一样的情况  

2)无法应对字符集大小极高的情况  

hash为解决上面的问题提供了很妙的方法。  

blue  

END  

之前一直以为字符串hash能做的事情Trie都能做。
然而现在知道有些事情，Hash能做，Trie不能做……

字符串hash的要点在于构造优秀的hash函数。有时为了避免冲突，用map存hash值也在所不惜。

详见课件？