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

浅析“最小表示法”思想在字符串循环同构问题中的应用 安徽省芜湖市第一中学 周源 【目录】浅析“最小表示法”思想在字符串循环同构问题中的应用 1 【目录】 1 【摘要】 2 【关键字】 2 【正文】 3 1、 问题引入 3 1. 明确几个记号和概念 3 2. 问题 3 2、 枚举算法和匹配算法 3 1. 枚举算法 3 2. 匹配算法 3 3. 小结 4 3、 最小表示法思想 4 1. “最小表示法”思想的提出 4 2. “最小表示法”思想的定义 4 3. “最小表示法”在本题的应用 5 4. 模拟算法执行 7 5. 小结 8 4、 总结 8【摘要】 最小表示法在有哪些信誉好的足球投注网站判重、判断图的同构等很多问题中有着重要的应用。本文就围绕字符串循环同构的判断这个问题，在很容易找到O(N)的匹配后，本文引进的“最小表示法”思想，并系统的对其下了定义，最后利用“最小表示法”思想构造出了更优秀，更自然的算法。 无论是增加“最小表示法”思想这方面的知识，提高增加竞赛中的综合素质，相信本文对同学们还是有所裨益的。 【关键字】 字符串 循环同构 匹配 最小表示法【正文】 问题引入 明确几个记号和概念 由于本篇论文主要讨论与字符串有关的算法，所以在本文中，一切未经说明的以开头的变量均表示字符串。 ⑴．，即的长度。 ⑵．为的第个字符。这里。 ⑶．，即截取出的第个字符到第个字符的子串。这里。特别的，。 ⑷．定义的一次循环；而的次循环，的零次循环。 ⑸．如果字符串可以经过有限次循环得到，即有，则称和是循环同构的。 ⑹．设有两个映射，定义和的连接，这里。——这个定义用于后文算法描述中。 问题 给定两个字符串和，，判断他们是否循环同构。 枚举算法和匹配算法 枚举算法 很容易知道，的不同的循环串最多只有个，即，所以只需要把他们一一枚举，然后分别与比较即可。 枚举算法思维简单，易于实现，而它的时间复杂度是级，已经可以胜任大多数问题的要求了。然而如果大至几十万，几百万，枚举算法就无能为力了，有没有更优秀的算法呢？ 匹配算法 从枚举算法执行过程中很容易发现，枚举算法的本质就是在一个可以循环的字符串中寻找的匹配，于是联想到模式匹配的改进算法是级的，那么在循环串中寻找匹配是不是也有线性的算法呢？回答是肯定的： 由于循环串与一般的字符串本质的区别就是前者是“循环”的，如果能去掉“循环”这个限制，那么就可以直接套用一般字符串的模式匹配算法了！显然，将复制两次：做为主串，则任何与循环同构的字符串至少都可以在中出现一次，于是可以说就是循环串的一般字符串形式！问题成功转化为求在中的模式匹配。——这完全可以在级时间内解决。 小结 很容易得到的枚举算法显然不能满足大数据的要求，于是我们从算法的执行过程入手，探查到了枚举算法的实质：模式匹配。最后，通过巧妙的构造、转换模型，直接套用模式匹配算法，得到了级别的算法。 但是问题是否已经完美解决了呢？也许你会说：以KMP算法为首的模式匹配改进算法，都是以难理解，难记忆著称的！这的确是KMP算法的缺点，而且其next数组繁琐的计算严重制约着算法的可扩展性，看来是有必要寻求更简洁的算法了。 最小表示法思想 “最小表示法”思想的提出 首先来看一个引例： [引例]有两列数，和，不记顺序，判断它们是否相同。 [分析]由于题目要求“不记顺序”，因此每一列数的不同形式高达种之多！如果要一一枚举，显然是不科学的。于是一种新的思想提出了：如果两列数是相同的，那么将它们排序之后得到的数列一定也是相同的。于是，算法复杂度迅速降为级。 这道题虽然简单，却给了我们一个重要的启示：当某两个对象有多种表达形式，且需要判断它们在某种变化规则下是否能够达到一个相同的形式时，可以将它们都按一定规则变化成其所有表达形式中的最小者，然后只需要比较两个“最小者”是否相等即可！ 下面我们系统的给出“最小表示法”思想的定义。 “最小表示法”思想的定义 设有事物集合和映射集合，其中是到的映射：。如果两个事物，有一系列映射的连接使，则说和是本质相同的。 这里满足： ⑴．任意，一定能在中一系列映射的连接的作用下，仍被映射至。 ⑵．任意，若有使，则一定存在一个或一系列映射，他们的连接。 由的性质⑴可知，和是本质相同的，即“本质相同”这个概念具有自反性。 从性质⑵可知，如果和是本质相同的，那么和也一定是本质相同的。即“本质相同”这个概念具有对称性。 另外，根据“本质相同”概念的定义很容易知道，“本质相同”这个概念具有传递性。即若和是本质相同，和是本质相同，那么一定有和是本质相同的。 给定和，如何判断中的两个事物和是否互为本质相同的呢？“最小表示法”就是可以应用于此类题目的一种思想。它规定中的所有事物均有一种特殊的大小关系。然后，根据中的变化规则，将和均化为规定大小关系中的最小者和，如果两者相同，则易知