1、浅析“最小表示法” 思想在字符串循环同构问题中的应用 安徽 周源浅析“ 最小表示法”思想在字符串循环同构问题中的应用安徽省芜湖市第一中学周源【目录】浅析“最小表示法” 思想在字符串循环同构问题中的应用 .1【目录】 .1【摘要】 .2【关键字】 .2【正文】 .31、 问题引入 .31. 明确几个记号和概念 .32. 问题 .32、 枚举算法和匹配算法 .31. 枚举算法 .32. 匹配算法 .33. 小结 .43、 最小表示法思想 .41. “最小表示法” 思想的提出 .42. “最小表示法” 思想的定义 .43. “最小表示法” 在本题的应用 .54. 模拟算法执行 .75. 小结 .84
2、、 总结 .8浅析“最小表示法” 思想在字符串循环同构问题中的应用 安徽 周源【摘要】最小表示法在搜索判重、判断图的同构等很多问题中有着重要的应用。本文就围绕字符串循环同构的判断这个问题，在很容易找到O(N)的匹配后，本文引进的“最小表示法” 思想，并系统的对其下了定义，最后利用“最小表示法 ”思想构造出了更优秀，更自然的算法。无论是增加“最小表示法 ”思想这方面的知识，提高增加竞赛中的综合素质，相信本文对同学们还是有所裨益的。【关键字】字符串 循环同构 匹配 最小表示法浅析“最小表示法” 思想在字符串循环同构问题中的应用 安徽 周源【正文】1、问题引入1. 明确几个记号和概念由于本篇论文主要
3、讨论与字符串有关的算法，所以在本文中，一切未经说明的以 开s头的变量均表示字符串。 ，即 的长度。s=length()s 为 的第 个字符。这里 。ii1is ，即截取出 的第 个字符到第 个字jcopy(,j+)ij符的子串。这里 。特别的， 。1isi=定义 的一次循环 ；而 的 次循环(1)2ssk(1)， 的零次循环 。(k)=)( (0)如果字符串 可以经过有限次循环得到 ，即有s，则称 和 是循环同构的。s2()Ns设有两个映射 ，定义 和 的连接f1,2:Af12，这里 。12(x)()x这个定义用于后文算法描述中。2. 问题给定两个字符串 和 ， ，判断他们是否循环同构。s=s
4、2、枚举算法和匹配算法1. 枚举算法很容易知道， 的不同的循环串最多只有 个，即11，所以只需要把他们一一枚举，然后分别与 比(0),(),(s1) s2较即可。枚举算法思维简单，易于实现，而它的时间复杂度是 级 1，已经可以胜任大O(N2)多数问题的要求了。然而如果 大至几十万，几百万，枚举算法就无能为力了，有没有N更优秀的算法呢？2. 匹配算法从枚举算法执行过程中很容易发现，枚举算法的本质就是在一个可以循环的字符串中寻找 的匹配，于是联想到模式匹配的改进算法是 级的，那么在循环串s12()中寻找匹配是不是也有线性的算法呢？回答是肯定的：由于循环串与一般的字符串本质的区别就是前者是“循环”的
5、，如果能去掉“循环”这个限1 这里N=|s1|=|s2|。浅析“最小表示法” 思想在字符串循环同构问题中的应用 安徽 周源制，那么就可以直接套用一般字符串的模式匹配算法了！显然，将 复制两次：s1做为主串，则任何与 循环同构的字符串至少都可以在 中出现一次，于S=s1+s1S是可以说 就是循环串 的一般字符串形式！问题成功转化为求 在 中的模式匹2配。这完全可以在 级时间内解决。O(N)3. 小结很容易得到的枚举算法显然不能满足大数据的要求，于是我们从算法的执行过程入手，探查到了枚举算法的实质：模式匹配。最后，通过巧妙的构造、转换模型，直接套用模式匹配算法，得到了 级别的算法。()但是问题是否
6、已经完美解决了呢？也许你会说：以KMP算法为首的模式匹配改进算法，都是以难理解，难记忆著称的！这的确是KMP算法的缺点，而且其 next数组繁琐的计算严重制约着算法的可扩展性，看来是有必要寻求更简洁的算法了。3、最小表示法思想1. “最小表示法”思想的提出首先来看一个引例：引例有两列数， 和 ，不记顺序，判断它们是a1,2nb1,2n否相同。分析由于题目要求“ 不记顺序 ”，因此每一列数的不同形式高达 种之多！如果要一!一枚举，显然是不科学的。于是一种新的思想提出了：如果两列数是相同的，那么将它们排序之后得到的数列一定也是相同的。于是，算法复杂度迅速降为 级。O(Nlog2)这道题虽然简单，却
7、给了我们一个重要的启示：当某两个对象有多种表达形式，且需要判断它们在某种变化规则下是否能够达到一个相同的形式时，可以将它们都按一定规则变化成其所有表达形式中的最小者，然后只需要比较两个“最小者 ”是否相等即可！下面我们系统的给出“最小表示法”思想的定义。2. “最小表示法”思想的定义设有事物集合 和映射集合 ，其中T=t1,2 nF=f1,2 m是 到 的映射： Tfi:。如果两个事物 ，有一系列fi(1m) stT映射的连接使 ，则说 和 是 本质相同的。Fi12 k(t)s这里 满足：任意 ，一定能在 中一系列映射的连接的作用下，仍被映射至 。tT t任意 ，若有 使 ，则一定存在一个或一
8、系列映射s,fF()=，他们的连接 。fi12 iki12 fik(t)s由 的性质可知， 和 是 本质相同的，即“本质相同”这个概念具有自反性。F从性质可知，如果 和 是 本质相同的，那么 和 也一定是 本质相同的ttF。即“ 本质相同” 这个概念具有对称性。(s,tT)另外，根据“本质相同” 概念的定义很容易知道，“ 本质相同 ”这个概念具有传递性。即若 和 是 本质相同， 和 是 本质相同，那么一定有 和 是1223F13本质相同的。浅析“最小表示法” 思想在字符串循环同构问题中的应用 安徽 周源给定 和 ，如何判断 中的两个事物 和 是否互为 本质相同的呢？“最小TFTstF表示法”就
9、是可以应用于此类题目的一种思想。它规定 中的所有事物均有一种特殊的大T小关系。然后，根据 中的变化规则，将 和 均化为规定大小关系中的最小者 m1和 ，如果两者相同，则易知， 和 本质相同， 和 本质相同，m2 112和 本质相同，所以 和 是本质相同的。否则，可以证明， 和 不是本质相tstst同的。3. “最小表示法”在本题的应用在本题中，事物集合 表示的是不同的字符串，而映射集合 则表示字符串的循环TF法则，“事物中的大小关系”就是字符串间的大小关系。那么，如何将最小表示法应用于本题呢？最简单的方法就是根据上文，分别求出 s1和 的最小表示，比较它们是否相同。如果要是很简单的这么做，问题
10、就非常麻烦了：s2求字符串的最小表示法虽然有 级算法，但是思路十分复杂，还不如匹配算法 O(N)如果单纯得这么做，就违背了我们寻找更好算法的初衷。这样，看上去“最小表示法”是无能为力了。然而我们换一种思路：和匹配算法相似，将 和 各复制一次： ， ；并设两s12u=s1+ws2个指针 和 分别指向 和 的第一个字符。ijuw设 ，也就是说函数M()=n1ks于0ij，从 第 个字符开头的循环串是 ，如图， 的x,+ks1x(x1)(x1)前 个字符是 ，当然，也可以表示为 ，对称的，可以(i)i i2注意，这里所说的“在原串中的位置” ，并不是单纯的在原串中寻找到的第一个匹配，而是以之开头的循
11、环串是原串的最小表示。u串：ixi+ki(i+k+1)|s1|w串：jj+(x-i)j+kj+k+1|s2|相等 大于浅析“最小表示法” 思想在字符串循环同构问题中的应用 安徽 周源在 串中找到一段字符 ，这两段字符串长度相等，而且根据上文wi+(x)jk假设的扫描过程可以得到 。而u1=wi(x)j+k1，所以得到 ，即ui+kj i。而根据假设 和 是循环同构的s(x1)ii()js2，那么一定能在 的所有循环串中找到一个字符串 ，满足它的前 个字s(ix)符是 。于是有 ，得 一定不是 的i()jk(x1)1)s最小表示。所以 不可能在 一段中，也就可以将指针 向后滑动M2i,+ i个字
12、符： 。(k+1i同理得到如果 ，可将指针 向后滑动 个字符：uwji(k+)；否则说明 ，就将指针 向后滑动 个字i1iwj iaab现在结果是 ，同理执行第三次：i=2,j3ubaabj于k=2 i+ubaawbj于ui+kwj i=aab此时已经是 ，执行第四次：i5,j3ubaa=bjk=s15于ui+kwj!i+kubaawbj浅析“最小表示法” 思想在字符串循环同构问题中的应用 安徽 周源这时发现 ！成功得出 和 是循环同构的，算法返回值为u59=w37s12真。5. 小结经过一番努力，我们终于得到了一个与匹配算法本质不同的线性算法。在这个问题中，“最小表示法 ”思想引导我们从问题
13、的另一方面分析，进而构造出一个全新的算法。比起匹配算法，它容易理解，便于记忆，实现起来，也不过是短短的几重循环，非常方便，便于应用于扩展问题。4、总结“最小表示法”是判断两种事物本质是否相同的一种常见思想，它的通用性也是被人们认可的无论是搜索中判重技术，还是判断图的同构之类复杂的问题，它都有着无可替代的作用。深入分析不难得出，该思想的精华在于引入了“序”这个概念，将待比较两个事物化为规定顺序中最小的（也可能是最大的）再加以比较。然而值得注意的是，在如今的信息学竞赛中，试题纷繁复杂，使用的算法也不再拘泥于几个经典的算法，改造经典算法或是将多种算法组合是常用的方法之一。正如本文讨论的问题，单纯的寻求字符串的最小表示显得得不偿失，但利用“最小表示法”的思想，和字符串的最小表示这个客观存在的事物，我们却找到了一个简单、优秀的算法。因此，在解决实际问题时，只有深入分析，敢于创新，才能将问题化纷繁为简洁，化无序为有序。化纷繁为简洁，化无序为有序。
