1.杨弋《Hash在信息学竞赛中一类应用》.ppt

Hash在信息学竞赛中的一类应用 安徽师范大学附属中学 杨弋 前言 前言 前言 例1.多维匹配 一维：在一个串中找另一个串第一次出现的位置 二维：在一个字符矩阵中找另一个字符矩阵第一次出现的位置 如果扩展到k(k≤10)维呢？ 例1.多维匹配 一维的情况：Rabin-Karp算法 例1.多维匹配 一维的情况：Rabin-Karp算法 例1.多维匹配 扩展到二维的情况 例1.多维匹配 扩展到二维的情况 例1.多维匹配 更高维的情况…… 例1.多维匹配 传统算法 O(k(N+M)) 难以理解 相对实现困难 多维Rabin-Karp O(kN+M) 易于理解 易于编写，不易出错 例1.多维匹配 回顾：我们是怎么计算出Hash值的？ 例2.树和图的同构 有根树 例2.树和图的同构 有根树 例2.树和图的同构 有根树 例2.树和图的同构 有根树 例2.树和图的同构 有根树 例2.树和图的同构 有根树，另一种办法 例2.树和图的同构 无根树 例2.树和图的同构 无根树 总结 Hash的本质 总结 结束 谢谢！ 例2.树和图的同构 为什么不直接用Rabin-Karp那样的先乘后加？ * * Hash Hash Hash CRC32! MD5! SHA-1! More… c a c a b a b c a b a c a b O(NM)? a b c × × × 1 p p2 a b c × × × 1 p p2 求和 × × p p2 × p3 a × 1 O(NM)? O(N+M)! [ ] q mod i X p M i X S pf S f M i i ] [ ] [ ) ( ) ( 1 - + + = + q mod ú ? ù ê ? é p i S S f S len i i S len ] [ ) ( ) ( 1 ) ( = ? = - a b a a c b b c a b a c ×p2 ×p ×p2 ×p2 ×p2 ×p ×p ×p ×q3 q3 q3 q2 q2 q q ×q2 ×q × p3 × p 1 × × p2 × p2 p × × p3 × p4 × 1 部分和？ 两端增加或者删除一位后的Hash值 计算两个串连接后的串的Hash值 O(1) O(1) 线段树！ Sparse Table! 分块！ 预处理！ 平衡树！ = ≠ 对每一个子树计算一个Hash值…… 1234 1234 1234 1234 1234 × 131 = 1417 (mod 2081) 1417 1417 1234 1234 (mod 2081) (( ×557)xor ×557)xor 924 × 131 = 346 1417 1417 346 68 68 516 ≠ ≠ O(n log n) 可以给出具体对应方案 可以使用Hash表在O(1)时间内查询 树→串 2 3 0 1 0 0 1 0 子树的顺序？ 字母序？ 按Hash值排序！ f(u,v)表示以u为v的父亲节点时以v为根的子树的Hash值 u v 类似地，有根森林，甚至任意图的同构问题也是可以使用Hash函数解决的 Hash 信息量大 不易比较 方便高效地比较 “概括” 化繁为简 正确性 优美性 有所舍弃？ 效率 简洁 扩展性 有所收获！ 题目 适合 理想的算法 自己 Leaf*(p2+p+1)*q*(p+1)*q (Leaf*(p+1)*q*p+ Leaf*(p3+p2+p+1)*q)*q ?的可能为 = = *