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

Hash在信息学竞赛中的一在信息学竞赛中的一类应用类应用安徽师范大学附属中学杨弋Hash在信息学竞赛中的一类应用安徽师范大学附属中学 杨弋1 1前言前言Hash前言Hash2 2前言前言Hash前言Hash3 3前言前言HashCRC32!MD5!SHA-1!More前言HashCRC32!MD5!SHA-1!More4 4例例1.多维匹配多维匹配n n一维：在一个串中找另一个串第一次出现的位置n n二维：在一个字符矩阵中找另一个字符矩阵第一次出现的位置n n如果扩展到k(k10)维呢？例1.多维匹配一维：在一个串中找另一个串第一次出现的位置5 5例例1.多维匹配多维匹配n n一维的情况：Rabin-Karp算法c a ca ba b c a b ac a bO(NM)?例1.多维匹配一维的情况：Rabin-Karp算法cacab6 6例例1.多维匹配多维匹配n n一维的情况：Rabin-Karp算法a b c1pp2ab c1pp2求和pp2p3a1O(NM)?O(N+M)!qmodiXpMiXSpfSfMii )()(1-+=+qmod piSSfSleniiSlen)()(1)(=-例1.多维匹配一维的情况：Rabin-Karp算法abc7 7例例1.多维匹配多维匹配n n扩展到二维的情况abaacbbcabacp2pp2p2p2pppq3q3q3q2q2qqq2q例1.多维匹配扩展到二维的情况abaacbbcabacp28 8例例1.多维匹配多维匹配n n扩展到二维的情况p3p1p2p2pp3p41例1.多维匹配扩展到二维的情况p3p1p2p2p9 9例例1.多维匹配多维匹配n n更高维的情况例1.多维匹配更高维的情况1010例例1.多维匹配多维匹配传统算法O(k(N+M)难以理解相对实现困难多维Rabin-KarpO(kN+M)易于理解易于编写，不易出错例1.多维匹配传统算法多维Rabin-Karp1111例例1.多维匹配多维匹配回顾：我们是怎么计算出Hash值的？部分和？两端增加或者删除一位后的两端增加或者删除一位后的HashHash值值计算两个串连接后的串的计算两个串连接后的串的HashHash值值O(1)O(1)O(1)O(1)线段树！Sparse Table!分块！预处理！平衡树！例1.多维匹配回顾：我们是怎么计算出Hash值的？部分和？两1212例例2.树和图的同构树和图的同构有根树=例2.树和图的同构有根树=1313例例2.树和图的同构树和图的同构有根树例2.树和图的同构有根树1414例例2.树和图的同构树和图的同构有根树对每一个子树计算一个Hash值12341234123412341234 131=1417(mod 2081)1417141712341234(mod 2081)(557)xor557)xor924 131=3461417141734668例2.树和图的同构有根树对每一个子树计算一个Hash值11515例例2.树和图的同构树和图的同构有根树68516 例2.树和图的同构有根树685161616例例2.树和图的同构树和图的同构有根树O(n log n)可以给出具体对应方案可以使用Hash表在O(1)时间内查询例2.树和图的同构有根树O(n log n)可以给出具体对应1717例例2.树和图的同构树和图的同构有根树，另一种办法树串23 01001 0子树的顺序？字母序？按Hash值排序！例2.树和图的同构有根树，另一种办法树串23010010子1818例例2.树和图的同构树和图的同构无根树f(u,v)表示以u为v的父亲节点时以v为根的子树的Hash值uv例2.树和图的同构无根树f(u,v)表示以u为v的父亲节点时1919例例2.树和图的同构树和图的同构无根树类似地，有根森林，甚至任意图的同构问题也是可以使用Hash函数解决的例2.树和图的同构无根树类似地，有根森林，甚至任意图的同构问2020总结总结Hash的本质Hash信息量大不易比较方便高效地比较“概括”化繁为简总结Hash的本质Hash信息量大方便高效地比较“概括”2121总结总结正确性优美性有所舍弃？效率简洁扩展性有所收获！题目适合理想的算法自己总结正确性优美性有所舍弃？效率简洁扩展性有所收获！题目适合理2222结束结束 谢谢！结束 谢谢！2323