［推荐精品］算法合集之《浅析“最小表示法”思想在字符串循环同构问题中的应用》.doc

《［推荐精品］算法合集之《浅析“最小表示法”思想在字符串循环同构问题中的应用》.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、肉析“最小表示法”恩想在字符串循环同构问题中的应用安徽省芜湖市第一-小学周源浅析“最小表示法”思想在字符串循环同构问题中的应用1【目录】1【摘要】2【关键字】2【正文】3一、问题引入31.明确几个记号和概念32.问题3二、枚举算法和匹配算法31.枚举算法32.匹配算法33.小结4三、最小表示法思想41.“最小表示法”思想的提岀42.“最小表示法”思想的定义43."最小表示法”在本题的应用54.模拟算法执行75.小结8四、总结8【摘要】最小表示法在搜索判重、判断图的同构等很多问题中有着重要的应用。本文就围绕字符串循环同构的判断这个问题，在很容易找到O(N)的匹配后，本文引进的

2、“最小表示法”思想，并系统的对其下了定义，最后利用“最小表示法”思想构造出了更优秀，更自然的算法。无论是增加“最小表示法”思想这方面的知识，提高增加竞赛中的综合素质，相信本文对同学们还是有所裨益的。【笑键字】字符串循环同构匹配最小表示法【正文】一、问题引入1.明确几个记号和概念由于木篇论文主要讨论与字符串有关的算法，所以在木文屮，一切未经说明的以，开头的变量均表示字符串。错误！未找到引用〔s=length(s),即s的长度。错误！未找到引用源。.s[i]为$的第'个字符。这里1GV£错误！未找到引用源o.s[i^=即截取出$的第'个字符到第）个字符的了串。这里15i/5s。

3、特别的，曲-»z]=s[i]o错误！未找到引用源。.定义s的一次循环5（，）=5[2T卜

4、]+川]；而$的比伙〉1）次循环=$伙一1）山,s的零次循环r。错误！未找到引用源。.如果字符串“可以经过有限次循环得到s2,即有52=sfkgN）,则称si和s2是循环同构的。错误！未找到引用源。.设有两个映射九，几：AtA,定义£和/的连接九•几（兀）=九（尢⑴），这里X"。——这个定义用于后文算法描述屮。2.问题给定两个字符串“和s2,卜1

5、=卜2

6、,判断他们是否循环同构。二、枚举算法和匹配算法1.枚举算法很容易知道，“的不同的循环串最多只有卜i

7、个，即s『，sr，・・・，s

8、T"T，所以只需要把他们一一-枚举，然后分别与S2比较即可。枚举算法思维简单，易于实现，而它的时间复杂度是o（n‘）级已经可以胜任大多数问题的要求了。然而如果N大至几卜力•，几百力•，枚举算法就无能为力了，有没有更优秀的算法呢?2.匹配算法从枚举算法执行过程屮很容易发现，枚举算法的本质就是在一个可以循环的字符串“中寻找s2的匹配，于是联想到模式匹配的改进算法是0（N）级的，那么在循环串中寻找I兀配'这里N=lsll=ls2l°是不是也有线性的算法呢？冋答是肯定的：由于循环串与一般的字符串本质的区别就是前者是“循环”的，如果能去掉“循环”这个限制，那么就可以直接套用一般字符串

9、的模式匹配算法了！显然，将“复制两次：5=51+51做为主串，则任何与S1循环同构的字符串至少都可以在S屮出现一次，于是可以说S就是循环串sl的一•般字符串形式！问题成功转化为求s2在S屮的模式匹配。——这完全可以在0(N)级时间内解决。3.小结很容易得到的枚举算法显然不能满足大数据的耍求，于是我们从算法的执行过程入手，探杏到了枚举算法的实质：模式匹配。最后，通过巧妙的构造、转换模型，直接套用模式匹配算法，得到了0(N)级别的算法。但是问题是否已经完美解决了呢？也许你会说：以KMP算法为首的模式匹配改进算法,祁是以难理解，难记忆著称的！这的确是KMP算法的缺点，而且Knex

10、t数组繁琐的计算严重制约着算法的可扩展性，看来是有必要寻求更简洁的算法了。三、最小表示法思想1・“最小表示法”思想的提出首先来看一个引例：［引例］有两列数,0,02,…Q”加bib?，…b”，不记顺序，判断它们是否相同。［分析］由于题1=1要求“不记顺序”，因此每一列数的不同形式高达川种z多！如果要一一枚举，显然是不科学的。于是一种新的思想提出了：如果两列数是相同的，那么将它们排序Z后得到的数列一定也是相同的。于是，算法复杂度迅速降为O(ZVlog.N)级。这道题虽然简单，却给了我们一个重要的启示：当某两个对象有多种表达形式，且需要判断它们在某种变化规则下是否能够达到一个相

11、同的形式时，可以将它们都按一定规则变化成其所有表达形式屮的最小者，然后只需要比较两个“最小者”是否相等即可！下面我们系统的给出“最小表示法”思想的定义。2・“最小表示法”思想的定义设有事物集合”仏並，…亿｝和映射集合F=，其屮/(l