国家集训队2007论文集1.杨弋《hash在信息学

国家集训队2007论文集1.杨弋《hash在信息学

ID:19854281

大小:1.05 MB

页数:24页

时间:2018-10-07

国家集训队2007论文集1.杨弋《hash在信息学_第1页
国家集训队2007论文集1.杨弋《hash在信息学_第2页
国家集训队2007论文集1.杨弋《hash在信息学_第3页
国家集训队2007论文集1.杨弋《hash在信息学_第4页
国家集训队2007论文集1.杨弋《hash在信息学_第5页
资源描述:

《国家集训队2007论文集1.杨弋《hash在信息学》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

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-++=+qmodú

2、ûùêëé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(1)线段树!Spars

3、eTable!分块!预处理!平衡树!例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.树和图的同构有根树,另一种办法树→串23010010子树的顺序?字母序?按Hash值排

4、序!例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½的可能为==

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。