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

浅析“最小表示法”思想在字符串循环同构问题中的应用安徽周源浅析“最小表示法”思想在字符串循环同构问题中的应用安徽省芜湖市第一中学周源【目录】浅析“最小表示法”思想在字符串循环同构问题中的应用...........................................................1【目录】...................................................................................................................................1【摘要】...................................................................................................................................2【关键字】...............................................................................................................................2【正文】...................................................................................................................................31、问题引入...................................................................................................................31.明确几个记号和概念..........................................................................................32.问题......................................................................................................................32、枚举算法和匹配算法...............................................................................................31.枚举算法..............................................................................................................32.匹配算法..............................................................................................................33.小结......................................................................................................................43、最小表示法思想.......................................................................................................41.“最小表示法”思想的提出...................................................................................42.“最小表示法”思想的定义...................................................................................43.“最小表示法”在本题的应用...............................................................................54.模拟算法执行......................................................................................................75.小结......................................................................................................................84、总结...........................................................................................................................8浅析“最小表示法”思想在字符串循环同构问题中的应用安徽周源【摘要】最小表示法在搜索判重、判断图的同构等很多问题中有着重要的应用。本文就围绕字符串循环同构的判断这个问题，在很容易找到O(N)的匹配后，本文引进的“最小表示法”思想，并系统的对其下了定义，最后利用“最小表示法”思想构造出了更优秀，更自然的算法。无论是增加“最小表示法”思想这方面的知识，提高增加竞赛中的综合素质，相信本文对同学们还是有所裨益的。【关键字】字符串循环同构匹配最小表示法浅析“最小表示法”思想在字符串循环同构问题中的应用安徽周源【正文】1、问题引入1.明确几个记号和概念由于本篇论文主要讨论与字符串有关的算法，所以在本文中，一切未经说明的以s开头的变量均表示字符串。⑴．∣s∣=length(s)，即s的长度。⑵．s[i]为s的第i个字符。这里1≤i≤∣s∣。⑶．s[i→j]=copy(s,i,j−i+1)，即截取出s的第i个字符到第j个字符的子串。这里1≤i≤j≤∣s∣。特别的，s[i→i]=s[i]。⑷．定义s的一次循环s(1)=s[2→∣s∣]+s[1]；而s的k(k1)次循环s(k)=s(k−1)(1)，s的零次循环s(0)=s。⑸．如果字符串s1可以经过有限次循环得到s2，即有s2=s1(k)(k∈N)，则称s1和s2是循环同构的。⑹．设有两个映射f1,f2:A→A，定义f1和f2的连接f1⋅f2(x)=f1(f2(x))，这里x∈A。——这个定义用于后文算法描述中。2.问题给定两个字符串s1和s2，∣s1∣=∣s2∣，判断他们是否循环同构。2、枚举算法和匹配算法1.枚举算法很容易知道，s1的不同的循环串最多只有∣s1∣个，即s1(0),s1(1),…,s1(∣s1∣−1)，所以只需要把他们一一枚举，然后分别与s2比较即可。枚举算法思维简单，易于实现，而它的时间复杂度是O(N2)级1，已经可以胜任大多数问题的要求了。然而如果N大至几十万，几百万，枚举算法就无能为力了，有没有更优秀的算法呢？2.匹配算法从枚举算法执行过程中很容易发现，枚举算法的本质就是在一个可以循环的字符串s11这里N=|s1|=|s2|。浅析“最小表示法”思想在字符串循环同构问题中的应用安徽周源中寻找s2的匹配，于是联想到模式匹配的改进算法是O(N)级的，那么在循环串中寻找匹配是不是也有线性的算法呢？回答是肯定的：由于循环串与一般的字符串本质的区别就是前者是“循环”的，如果能去掉“循环”这个限制，那么就可以直接套用一般字符串的模式匹配算法了！显然，将s1复制两次：S=s1+s1做为主串，则任何与s1循环同构的字符串至少都可以在S中出现一次，于是可以说S就是循环串s1的一般字符串形式！问题成功转化为求s2在S中的模式匹配。——这完全可以在O(N)级时间内解决。3.小结很容易得到的枚举算法显然不能满足大数据的要求，于是我们从算法的执行过程入手，探查到了枚举算法的实质：模式匹配。最后，通过巧妙的构造、转换模型，直接套用模式匹配算法，得到了O(N)级别的算法。但是问题是否已经完美解决了呢？也许你会说：以KMP算法为首的模式匹配改进算法，都是以难理解，难记忆著称的！这的确是KMP算法的缺点，而且其next数组繁琐的计算严重制约着算法的可扩展性，看来是有必要寻求更简洁的算法了。3、最小表示法思想1.“最小表示法”思想的提出首先来看一个引例：[引例]有两列数，a1,a2,…an和b1,b2,…bn，不记顺序，判断它们是否相同。[分析]由于题目要求“不记顺序”，因此每一列数的不同形式高达n!种之多！如果要一一枚举，显然是不科学的。于是一种新的思想提出了：如果两列数是相同的，那么将它们排序之后得到的数列一定也是相同的。于是，算法复杂度迅速降为O(Nlog2N)级。这道题虽然简单，却给了我们一个重要的启示：当某两个对象有多种表达形式，且需要判断它们在某种变化规则下是否能够达到一个相同的形式时，可以将它们都按一定规则变化成其所有表达形式中的最小者，然后只需要比较两个“最小者”是否相等即可！下面我们系统的给出“最小表示法”思想的定义。2.“最小表示法”思想的定义设有事物集合T={t1,t2,⋯,tn}和映射集合F={f1,f2,⋯,fm}，其中fi(1≤i≤m)是T到T的映射：TTfi:。如果两个事物s,t∈T，有一系列F映射的连接使fi1⋅fi2⋅⋯⋅fik(t)=s，则说s和t是F本质相同的。这里F满足：⑴．任意t∈T，一定能在F中一系列映射的连接的作用下，仍被映射至t。⑵．任意s,t∈T，若有f∈F使f(s)=t，则一定存在一个或一系列映射浅析“最小表示法”思想在字符串循环同构问题中的应用安徽周源fi1,fi2,⋯,fik∈F，他们的连接fi1⋅fi2⋅⋯⋅fik(t)=s。由F的性质⑴可知，s和s是F本质相同的，即“本质相同”这个概念具有自反性。从性质⑵可知，如果s和t是F本质相同的，那么t和s也一定是F本质相同的(s,t∈T)。即“本质相同”这个概念具有对称性。另外，根据“本质相同”概念的定义很容易知道，“本质相同”这个概念具有传递性。即若t1和t2是F本质相同，t2和t3是F本质相同，那么一定有t1和t3是F本质相同的。给定T和F，如何判断T中的两个事物s和t是否互为F本质相同的呢？“最小表示法”就是可以应用于此类题目的一种思想。它规定T中的所有事物均有一种特殊的大小关系。然后，根据F中的变化规则，将s和t均化为规定大小关系中的最小者m1和m2，如果两者相同，则易知，s和m1本质相同，m1和m2本质相同，m2和t本质相同，所以s和t是本质相同的。否则，可以证明，s和t不是本质相同的。3.“最小表示法”在本题的应用在本题中，事物集合T表示的是不同的字符串，而映射集合F则表示字符串的循环法则，“事物中的大小关系”就是字符串间的大小关系。那么，如何将最小表示法应用于本题呢？最简单的方法就是根据上文，分别求出s1和s2的最小表示，比较它们是否相同。如果要是很简单的这么做，问题就非常麻烦了：求字符串的最小表示法虽然有O(N)级算法，但是思路十分复杂，还不如匹配算法——如果单纯得这么做，就违背了我们寻找更好算法的初衷。这样，看上去“最小表示法”是无能为力了。然而我们换一种思路：和匹配算法相似，将s1和s2各复制一次：u=s1+s1，w=s2+s2；并设两个指针i和j分别指向u和w的第一个字符。设M(s)=min1≤k≤∣s∣{任意0≤i∣s∣，均有s(k−1)≥s(i)}，也就是说函数M(s)返回的是s最小表示串的第一个字符在原