最小表示法PPT课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,.,#,最小表示法在,字符串循环同构中的应用,主讲人：孙权,ACMLab,519HNAU,一、问题引入,二、算法流程,三、例题推荐,参考资料：周源,(,最小表示法,).ppt,1,.,什么是同构？,有两条环状的项链，每条项链上各有,N,个多种颜色的珍珠，相同颜色的珍珠，被视为相同。,1,1,2,.,前言,“最小表示法”比起动态规划、贪心等思想，在当今竞赛中似乎并不是很常见。但是在解决判断“同构”一类问题中却起着重要的作用。,本文即将讨论字符串中的同构问题，如何巧妙地运用最小表示法来解题呢，让我们继续一起思考吧。3,.,例题分析,poj1509,(,英文题太长了）,，,直接上题意,:,题意：给你一个,字符串，将字符串第,i,位开始的字串提到前面形成,Ai,求,n,个这种串中,字典序最小的串,的,i,。,Input,2,aaabaaa,helloworld,Output,5,10,4,.,题解,方法一：暴力,O(n2);,方法二：传说中的“最小表示法”！,!,5,.,定义：“最小表示法”,但在循环字符串,的最小表示法可以通俗的理解为,：,对于一个字符串,S,，求,S,的循环的同构字符串,S,中字典序最小的一个。,定义：,设有,事物集合,T=t1,，,t2,，,，,tn,，,映射集合,F=f1,，,f2fm,。,任意,fF,均为,T,到,T,的映射，,fi:TT,。,如果,两个事物,s,t T,，有,一系列,F,的映射的,连接,fi1fi2,fik(s)=t,，则,说,s,和,t,是,F,本质相同,的。,不明觉,厉！,6,.,算法流程,1.,两,个指针,i=0,j=1,.,2.,从,si,和,sj,开始,比较，,字符,si+k,和,字符,sj+k,是否,相同,当,k=len,时,返回,i,j,中的最小值,.,3.,当,si+k,和,sj+k,不相同时,若,si+ksj+k,则,可见从,si+1,到,si+k,都不会是最小字典序的起始位置,所以,i=i+k+1.,当,si+ksj+k时同理,.,4.,若移动,后,i=,j,则使,i+,或者,j+;,还是看图最实际啦！,不怎么理解？有点抽象！,7,.,总之两句话,总之,（,1,）当两个字符相同时，一直向前比较,直到,k=len;,（,2,）两指针向后滑动比较失败以后，,指向,较大字符的指针向后滑动,k+1,个位置。,下面让我们将这种方法应用于一个实例。,8,.,看图解,1,(,其中,k,为每次成功匹配的个数）,设,s1=babba,，,s2=bbaba,。,u=b a b b a b a b b a,w=b b a b a b b a b a,i,j,比较失败时,k=1,不相等,因为,ui+kwj+k,所以移动指针,i,ji,比较失败时,k=0,10,.,看,图解,3,(,其中,k,为每次成功匹配的个数）,设,s1=babba,，,s2=bbaba,。,u=b a b b a b a b b a,w=b b a b a b b a b a,不相等,因为,ui+kwj+k,所以移动指针,i,j,i,i,比较失败时,k=2,为什么较大的向前跳,k+1,，因为,0,k,任一字符开头，下面都存在一个比它小的一个,字符串,11,.,看,图解,4,(,其中,k,为每次成功匹配的个数）,设,s1=babba,，,s2=bbaba,。,u=b a b b a b a b b a,w=b b a b a b b a b a,j,i,u5,9=w3,7,！,所以,s1,和,s2,是循环同构的！,12,.,Attention,注意最小表示法 是针对单个字符串，在一个字符串中匹配，上面的图解为了更清晰，所以画了两个字符串。,最后我们再来理解一下为什么这个算法是正确的,back,13,.,例题推荐,poj 1509,hdu 2609,14,.,