1杨弋《Hash在信息学竞赛中的一类应用》课件

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

][][)()(1-++=+qmod

úûùêëépiSSfSleniiSlen][)()(1)(=å=-例1.多维匹配一维的情况：Rabin-Karp算法abc××7例1.多维匹配扩展到二维的情况abaacbbcabac×p2×p×p2×p2×p2×p×p×p×q3q3q3q2q2qq×q2×q例1.多维匹配扩展到二维的情况abaacbbcabac×p28例1.多维匹配扩展到二维的情况×p3×p1××p2×p2p××p3×p4×1例1.多维匹配扩展到二维的情况×p3×p1××p2×p2p×9例1.多维匹配更高维的情况……例1.多维匹配更高维的情况……10例1.多维匹配传统算法O(k(N+M))难以理解相对实现困难多维Rabin-KarpO(kN+M)易于理解易于编写，不易出错例1.多维匹配传统算法多维Rabin-Karp11例1.多维匹配回顾：我们是怎么计算出Hash值的？部分和？两端增加或者删除一位后的Hash值计算两个串连接后的串的Hash值O(1)O(1)线段树！SparseTable!分块！预处理！平衡树！例1.多维匹配回顾：我们是怎么计算出Hash值的？部分和？两12例2.树和图的同构有根树=≠例2.树和图的同构有根树=≠13例2.树和图的同构有根树例2.树和图的同构有根树14例2.树和图的同构有根树对每一个子树计算一个Hash值……12341234123412341234×131=1417(mod2081)1417141712341234(mod2081)((×557)xor×557)xor924×131=3461417141734668例2.树和图的同构有根树对每一个子树计算一个Hash值……115例2.树和图的同构有根树68516≠≠例2.树和图的同构有根树68516≠≠16例2.树和图的同构有根树O(nlogn)可以给出具体对应方案可以使用Hash表在O(1)时间内查询例2.树和图的同构有根树O(nlogn)可以给出具体对应17例2.树和图的同构有根树，另一种办法树→串23010010子树的顺序？字母序？按Hash值排序！例2.树和图的同构有根树，另一种办法树→串23010010子18例2.树和图的同构无根树f(u,v)表示以u为v的父亲节点时以v为根的子树的Hash值uv例2.树和图的同构无根树f(u,v)表示以u为v的父亲节点时19例2.树和图的同构无根树类似地，有根森林，甚至任意图的同构问题也是可以使用Hash函数解决的例2.树和图的同构无根树类似地，有根森林，甚至任意图的同构问20总结Hash的本质Hash信息量大不易比较方便高效地比较“概括”化繁为简总结Hash的本质Hash信息量大方便高效地比较“概括”21总结正确性优美性有所舍弃？效率简洁扩展性有所收获！题目适合理想的算法自己总结正确性优美性有所舍弃？效率简洁扩展性有所收获！题目适合理22结束谢谢！结束谢谢！23例2.树和图的同构为什么不直接用Rabin-Karp那样的先乘后加？Leaf*(p2+p+1)*q*(p+1)*q(Leaf*(p+1)*q*p+Leaf*(p3+p2+p+1)*q)*q½的可能为==例2.树和图的同构为什么不直接用Rabin-Karp那样的先24Hash在信息学竞赛中的一类应用安徽师范大学附属中学 杨弋Hash在信息学竞赛中的一类应用安徽师范大学附属中学 杨弋25前言Hash前言Hash26前言Hash前言Hash27前言HashCRC32!MD5!SHA-1!More…前言HashCRC32!MD5!SHA-1!More…28例1.多维匹配一维：在一个串中找另一个串第一次出现的位置二维：在一个字符矩阵中找另一个字符矩阵第一次出现的位置如果扩展到k(k≤10)维呢？例1.多维匹配一维：在一个串中找另一个串第一次出现的位置29例1.多维匹配一维的情况：Rabin-Karp算法cacababcabacabO(NM)?例1.多维匹配一维的情况：Rabin-Karp算法cacab30例1.多维匹配一维的情况：Rabin-Karp算法abc×××1pp2abc×××1pp2求和××pp2×p3a×1O(NM)?O(N+M)![]qmodiXpMiXSpfSfMii

][][)()(1-++=+qmod

úûùêëépiSSfSleniiSlen][)()(1)(=å=-例1.多维匹配一维的情况：Rabin-Karp算法abc××31例1.多维匹配扩展到二维的情况abaacbbcabac×p2×p×p2×p2×p2×p×p×p×q3q3q3q2q2qq×q2×q例1.多维匹配扩展到二维的情况abaacbbcabac×p232例1.多维匹配扩展到二维的情况×p3×p1××p2×p2p××p3×p4×1例1.多维匹配扩展到二维的情况×p3×p1××p2×p2p×33例1.多维匹配更高维的情况……例1.多维匹配更高维的情况……34例1.多维匹配传统算法O(k(N+M))难以理解相对实现困难多维Rabin-KarpO(kN+M)易于理解易于编写，不易出错例1.多维匹配传统算法多维Rabin-Karp35例1.多维匹配回顾：我们是怎么计算出Hash值的？部分和？两端增加或者删除一位后的Hash值计算两个串连接后的串的Hash值O(1)O(1)线段树！SparseTable!分块！预处理！平衡树！例1.多维匹配回顾：我们是怎么计算出Hash值的？部分和？两36例2.树和图的同构有根树=≠例2.树和图的同构有根树=≠37例2.树和图的同构有根树例2.树和图的同构有根树38例2.树和图的同构有根树对每一个子树计算一个Hash值……12341234123412341234×131=1417(mod2081)1417141712341234(mod2081)((×557)xor×557)xor924×131=3461417141734668例2.树和图的同构有根树对每一个子树计算一个Hash值……139例2.树和图的同构有根树68516≠≠例2.树和图的同构有根树68516≠≠40例2.树和图的同构有根树O(nlogn)可以给出具体对应方案可以使用Hash表在O(1)时间内查询例2.树和图的同构有根树O(nlogn)可以给出具体对应41例2.树和图的同构有根树，另一种办法树→串23010010子树的顺序？字母序？按Hash值排序！例2.树和图的同构有根树，另一种办法树→串23010010子42例2.树和图的同构无根树f(u,v)表示以u为v的父亲节点时以v为根的子树的Hash值uv例2.树和图的同构无根树f(u,v)表示以u为v的父亲节点时43例2.树和图的同构无根树类似地，有根森林，甚至任意图的同构问题也是可以使用Hash函数解决的例2.树和图的同构无根树类似地，有根森林，甚至任意图的同构问44总结Hash的本质Hash信息量大不易比较方便高效地比较“概括”化繁为简总结Hash的本质Hash信息量大方便高效地比较“概括”45总结正确性优美性有所舍弃？效率简洁扩展性有所收获！