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

上传人(卖家):晟晟文业 文档编号:4349496 上传时间:2022-12-01 格式:PPT 页数:24 大小:1.07MB
下载 相关 举报
1杨弋《Hash在信息学竞赛中的一类应用》课件.ppt_第1页
第1页 / 共24页
1杨弋《Hash在信息学竞赛中的一类应用》课件.ppt_第2页
第2页 / 共24页
1杨弋《Hash在信息学竞赛中的一类应用》课件.ppt_第3页
第3页 / 共24页
1杨弋《Hash在信息学竞赛中的一类应用》课件.ppt_第4页
第4页 / 共24页
1杨弋《Hash在信息学竞赛中的一类应用》课件.ppt_第5页
第5页 / 共24页
点击查看更多>>
资源描述

1、HashHashHashCRC32!MD5!SHA-1!Morec a ca ba b c a b ac a bO(NM)?a b c1pp2ab c1pp2求和pp2p3a1O(NM)?O(N+M)!qmodiXpMiXSpfSfMii )()(1-+=+qmod piSSfSleniiSlen)()(1)(=-abaacbbcabacp2pp2p2p2pppq3q3q3q2q2qqq2qp3p1p2p2pp3p41部分和?线段树!Sparse Table!分块!预处理!平衡树!=对每一个子树计算一个Hash值12341234123412341234 131=1417(mod 2081)14

2、17141712341234(mod 2081)(557)xor557)xor924 131=346141714173466868516 O(n log n)可以给出具体对应方案可以使用Hash表在O(1)时间内查询树串23 01001 0子树的顺序?字母序?按Hash值排序!f(u,v)表示以u为v的父亲节点时以v为根的子树的Hash值uv类似地,有根森林,甚至任意图的同构问题也是可以使用Hash函数解决的Hash信息量大不易比较方便高效地比较“概括”化繁为简正确性优美性有所舍弃?效率简洁扩展性有所收获!题目适合理想的算法自己Leaf*(p2+p+1)*q*(p+1)*q(Leaf*(p+1)*q*p+Leaf*(p3+p2+p+1)*q)*q的可能为=

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 办公、行业 > 各类PPT课件(模板)
版权提示 | 免责声明

1,本文(1杨弋《Hash在信息学竞赛中的一类应用》课件.ppt)为本站会员(晟晟文业)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!


侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|