算法合集之浅析最小表示法思想在字符串循环同构问题中的应用.pptx
《算法合集之浅析最小表示法思想在字符串循环同构问题中的应用.pptx》由会员分享,可在线阅读,更多相关《算法合集之浅析最小表示法思想在字符串循环同构问题中的应用.pptx(40页珍藏版)》请在咨信网上搜索。
1、IOI2003冬令营演示文稿安徽周源浅析“最小表示法”思想在字符串循环同构问题中的应用安徽省芜湖市第一中学周 源 IOI2003冬令营演示文稿安徽周源前言“最最小小表表示示法法”比比起起动动态态规规划划、贪贪心心等等思思想想,在在当当今今竞竞赛赛中中似似乎乎并并不不是是很很常常见见。但但是是在在解解决决判判断断“同同构构”一一类类问问题题中中却却起着重要的作用。起着重要的作用。本本文文即即将将讨讨论论字字符符串串中中的的同同构构问问题题,如如何何巧巧妙妙地地运运用用最最小小表表示示法法来来解解题题呢呢,让让我我们继续一起思考吧。们继续一起思考吧。IOI2003冬令营演示文稿安徽周源问题引入有两
2、条环状的项链,每条项链上各有N个多种颜色的珍珠,相同颜色的珍珠,被视为相同。问题:判断两条项链是否相同。简单分析:由于项链是环状的,因此循环以后的项链被视为相同的,如图的两条项链就是一样的。IOI2003冬令营演示文稿安徽周源明确几个记号和概念|s|=length(s),即s的长度。1ij|s|s串:si为s的第i个字符。sij=copy(s,i,j-i+1)。这里1 i j|s|。sijIOI2003冬令营演示文稿安徽周源明确几个记号和概念定义s的一次循环s(1)=s2|s|+s1;s的k次循环(k1)s(k)为s(k-1)的一次循环;s的0次循环s(0)=s。12ij|s|s串:12ij|
3、s|S(1)串:IOI2003冬令营演示文稿安徽周源明确几个记号和概念如果字符串s1可以经过有限次循环得到s2,则称s1和s2是循环同构的。例如:s1和s2是循环同构的!s1=a b c db c d a一次循环s2=c d a b一次循环IOI2003冬令营演示文稿安徽周源明确几个记号和概念设有两个映射f1,f2:AA,定义f1和f2的连接f1f2(x)=f1(f2(x)。IOI2003冬令营演示文稿安徽周源问题的数学语言表达形式给定两个长度相等的字符串,|s1|=|s2|,判断它们是否是循环同构的。IOI2003冬令营演示文稿安徽周源枚举算法易知,s1的不同的循环串最多只有|s1|个,即s
4、1,s1(1),s1(2),s1(|s1|-1),所以只需要把他们一一枚举,然后分别与s2比较即可。IOI2003冬令营演示文稿安徽周源枚举算法优点:思维简单,易于实现。时间复杂度是O(N2)级(N=|s1|=|s2|)。如果N大一些,几十万,几百万Time Limit Exceeded!IOI2003冬令营演示文稿安徽周源构造新的算法首先构造新的模型:S=s1+s1为主串,s2为模式串。如果s1和s2是循环同构的,那么s2就一定可以在S中找到匹配!IOI2003冬令营演示文稿安徽周源匹配算法:理论的下界在S中寻找s2的匹配是有很多O(N)级的算法的。本题最优算法的时空复杂度均为O(N)级。这
5、已经是理论的下界了。IOI2003冬令营演示文稿安徽周源小结:枚举和匹配算法很容易得到的枚举算法显然不能满足大数据的要求,于是我们从算法的执行过程入手,探查到了枚举算法的实质:模式匹配。最后,通过巧妙的构造、转换模型,直接套用模式匹配算法,得到了O(N)级的算法。IOI2003冬令营演示文稿安徽周源探索新的算法但是问题是否已经完美解决了呢?KMP算法的缺点:难理解,难记忆;可扩展性不强。IOI2003冬令营演示文稿安徽周源引例有两列数a1,a2an和b1,b2bn,不记顺序,判断它们是否相同。an:4 2 6 3bn:6 2 3 4相同的两列数IOI2003冬令营演示文稿安徽周源分析由于题目要
6、求“不记顺序”,因此每一列数的不同形式高达n!种之多!如果要一一枚举,显然是不科学的。如果两列数是相同的,那么将它们排序之后得到的数列一定也是相同的。an:4 2 6 3bn:6 2 3 4排序后an:2 3 4 6bn:2 3 4 6相同IOI2003冬令营演示文稿安徽周源小结:引例这道题虽然简单,却给了我们一个重要的启示:当某两个对象有多种表达形式,且需要判断它们在某种变化规则下是否能够达到一个相同的形式时,可以将它们都按一定规则变化成其所有表达形式中的最小者,然后只需要比较两个“最小者”是否相等即可!IOI2003冬令营演示文稿安徽周源定义:“最小表示法”设有事物集合T=t1,t2,tn
7、,映射集合F=f1,f2,fm。任意fF均为T到T的映射,fi:TT。如果两个事物s,t T,有一系列F的映射的连接fi1fi2fik(s)=t,则说s和t是F本质相同的。IOI2003冬令营演示文稿安徽周源定义:“最小表示法”其中F满足两个条件:任意tT,一定能在F中一系列映射的连接的作用下,仍被映射至t。即任意一个事物tT,它和自己是F本质相同的。任意s,tT,若在F的一系列映射作用下,s和t是F本质相同的。那么一定有另一系列属于F的映射作用下,t和s是F本质相同的。即“本质相同”这个概念具有自反性。即“本质相同”这个概念具有对称性。IOI2003冬令营演示文稿安徽周源定义:“最小表示法”
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 浅析 最小 表示 思想 字符串 循环 同构 问题 中的 应用
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。