浅析“最小表示法”思想在字符串循环同构问题中的应用

《浅析“最小表示法”思想在字符串循环同构问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、浅析“最小表示法”思想在字符串循环同构问题中的应用安徽周源浅析“最小表示法”思想在字符串循环同构问题中的应用安徽省芜湖市第一中学周源【目录】浅析“最小表示法”思想在字符串循环同构问题中的应用安徽周源浅析“最小表示法”思想在字符串循环同构问题中的应用1【目录】1【摘要】2【关键字】2【正文】31、问题引入31.明确几个记号和概念32.问题32、枚举算法和匹配算法31.枚举算法32.匹配算法33.小结43、最小表示法思想41.“最小表示法”思想的提出42.“最小表示法”思想的定义43.“最小表示法”在本题的应用54.模拟算法执行75.小结84、总结8浅析“最小表示法”思想在字符串循环同构

2、问题中的应用安徽周源浅析“最小表示法”思想在字符串循环同构问题中的应用安徽周源【摘要】最小表示法在搜索判重、判断图的同构等很多问题中有着重要的应用。本文就围绕字符串循环同构的判断这个问题，在很容易找到O(N)的匹配后，本文引进的“最小表示法”思想，并系统的对其下了定义，最后利用“最小表示法”思想构造出了更优秀，更自然的算法。无论是增加“最小表示法”思想这方面的知识，提高增加竞赛中的综合素质，相信本文对同学们还是有所裨益的。【关键字】字符串循环同构匹配最小表示法浅析“最小表示法”思想在字符串循环同构问题中的应用安徽周源【正文】1、问题引入1.明确几个记号和概念由于本篇论文主要讨论与字符

3、串有关的算法，所以在本文中，一切未经说明的以开头的变量均表示字符串。⑴．，即的长度。⑵．为的第个字符。这里。⑶．，即截取出的第个字符到第个字符的子串。这里。特别的，。⑷．定义的一次循环；而的次循环，的零次循环。⑸．如果字符串可以经过有限次循环得到，即有，则称和是循环同构的。⑹．设有两个映射，定义和的连接，这里。——这个定义用于后文算法描述中。2.问题给定两个字符串和，，判断他们是否循环同构。2、枚举算法和匹配算法1.枚举算法很容易知道，的不同的循环串最多只有个，即，所以只需要把他们一一枚举，然后分别与比较即可。枚举算法思维简单，易于实现，而它的时间复杂度是级这里N=

4、s1

5、=

6、s2

7、

8、。，已经可以胜任大多数问题的要求了。然而如果大至几十万，几百万，枚举算法就无能为力了，有没有更优秀的算法呢？2.匹配算法从枚举算法执行过程中很容易发现，枚举算法的本质就是在一个可以循环的字符串浅析“最小表示法”思想在字符串循环同构问题中的应用安徽周源中寻找的匹配，于是联想到模式匹配的改进算法是级的，那么在循环串中寻找匹配是不是也有线性的算法呢？回答是肯定的：由于循环串与一般的字符串本质的区别就是前者是“循环”的，如果能去掉“循环”这个限制，那么就可以直接套用一般字符串的模式匹配算法了！显然，将复制两次：做为主串，则任何与循环同构的字符串至少都可以在中出现一次，于是可以说就是循环串的一

9、般字符串形式！问题成功转化为求在中的模式匹配。——这完全可以在级时间内解决。1.小结很容易得到的枚举算法显然不能满足大数据的要求，于是我们从算法的执行过程入手，探查到了枚举算法的实质：模式匹配。最后，通过巧妙的构造、转换模型，直接套用模式匹配算法，得到了级别的算法。但是问题是否已经完美解决了呢？也许你会说：以KMP算法为首的模式匹配改进算法，都是以难理解，难记忆著称的！这的确是KMP算法的缺点，而且其next数组繁琐的计算严重制约着算法的可扩展性，看来是有必要寻求更简洁的算法了。2、最小表示法思想1.“最小表示法”思想的提出首先来看一个引例：[引例]有两列数，和，不记顺序，判断它们是

10、否相同。[分析]由于题目要求“不记顺序”，因此每一列数的不同形式高达种之多！如果要一一枚举，显然是不科学的。于是一种新的思想提出了：如果两列数是相同的，那么将它们排序之后得到的数列一定也是相同的。于是，算法复杂度迅速降为级。这道题虽然简单，却给了我们一个重要的启示：当某两个对象有多种表达形式，且需要判断它们在某种变化规则下是否能够达到一个相同的形式时，可以将它们都按一定规则变化成其所有表达形式中的最小者，然后只需要比较两个“最小者”是否相等即可！下面我们系统的给出“最小表示法”思想的定义。2.“最小表示法”思想的定义设有事物集合和映射集合，其中是到的映射：。如果两个事物，有一系列映射

11、的连接使，则说和是本质相同的。这里满足：⑴．任意，一定能在中一系列映射的连接的作用下，仍被映射至。⑵．任意，若有使，则一定存在一个或一系列映射，他们的连接。由的性质⑴可知，和是本质相同的，即“本质相同”这个概念具有自反性。从性质⑵可知，如果和是本质相同的，那么和也一定是本质相同的浅析“最小表示法”思想在字符串循环同构问题中的应用安徽周源。即“本质相同”这个概念具有对称性。另外，根据“本质相同”概念的定义很容易知道，“本质相同”这个概念具有传递性。即若和是本