算法合集之《Hash在信息学竞赛中的一类应用》.ppt

《算法合集之《Hash在信息学竞赛中的一类应用》.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Hash在信息学竞赛中的一类应用安徽师范大学附属中学杨弋前言Hash前言Hash前言HashCRC32!MD5!SHA-1!More…例1.多维匹配一维：在一个串中找另一个串第一次出现的位置二维：在一个字符矩阵中找另一个字符矩阵第一次出现的位置如果扩展到k(k≤10)维呢？例1.多维匹配一维的情况：Rabin-Karp算法cacababcabacabO(NM)?例1.多维匹配一维的情况：Rabin-Karp算法abc×××1pp2abc×××1pp2求和××pp2×p3a×1O(NM)?O(N+M)![]qmodiXpMiXSpfSfMii][][)()(1-++=

2、+qmodúûùêëépiSSfSleniiSlen][)()(1)(=å=-例1.多维匹配扩展到二维的情况abaacbbcabac×p2×p×p2×p2×p2×p×p×p×q3q3q3q2q2qq×q2×q例1.多维匹配扩展到二维的情况×p3×p1××p2×p2p××p3×p4×1例1.多维匹配更高维的情况……例1.多维匹配传统算法O(k(N+M))难以理解相对实现困难多维Rabin-KarpO(kN+M)易于理解易于编写，不易出错例1.多维匹配回顾：我们是怎么计算出Hash值的？部分和？两端增加或者删除一位后的Hash值计算两个串连接后的串的Hash值O(1)O

3、(1)线段树！SparseTable!分块！预处理！平衡树！例2.树和图的同构有根树=≠例2.树和图的同构有根树例2.树和图的同构有根树对每一个子树计算一个Hash值……12341234123412341234×131=1417(mod2081)1417141712341234(mod2081)((×557)xor×557)xor924×131=3461417141734668例2.树和图的同构有根树68516≠≠例2.树和图的同构有根树O(nlogn)可以给出具体对应方案可以使用Hash表在O(1)时间内查询例2.树和图的同构有根树，另一种办法树→串2301001

4、0子树的顺序？字母序？按Hash值排序！例2.树和图的同构无根树f(u,v)表示以u为v的父亲节点时以v为根的子树的Hash值uv例2.树和图的同构无根树类似地，有根森林，甚至任意图的同构问题也是可以使用Hash函数解决的总结Hash的本质Hash信息量大不易比较方便高效地比较“概括”化繁为简总结正确性优美性有所舍弃？效率简洁扩展性有所收获！题目适合理想的算法自己结束谢谢！例2.树和图的同构为什么不直接用Rabin-Karp那样的先乘后加？Leaf*(p2+p+1)*q*(p+1)*q(Leaf*(p+1)*q*p+Leaf*(p3+p2+p+1)*q)*q½的可能

5、为==