最小表示法在字符串循环同构问题中的应用

IOI2003冬令营演示文稿安徽周源浅析“最小表示法”思想在字符串循环同构问题中的应用安徽省芜湖市第一中学周源IOI2003冬令营演示文稿安徽周源前言“最小表示法”比起动态规划、贪心等思想，在当今竞赛中似乎并不是很常见。但是在解决判断“同构”一类问题中却起着重要的作用。本文即将讨论字符串中的同构问题，如何巧妙地运用最小表示法来解题呢，让我们继续一起思考吧。IOI2003冬令营演示文稿安徽周源问题引入有两条环状的项链，每条项链上各有N个多种颜色的珍珠，相同颜色的珍珠，被视为相同。问题：判断两条项链是否相同。简单分析：由于项链是环状的，因此循环以后的项链被视为相同的，如图的两条项链就是一样的。IOI2003冬令营演示文稿安徽周源明确几个记号和概念⑴．|s|=length(s)，即s的长度。1…i…j…|s|s串：⑵．s[i]为s的第i个字符。⑶．s[i→j]=copy(s,i,j-i+1)。这里1≤i≤j≤|s|。s[i→j]IOI2003冬令营演示文稿安徽周源明确几个记号和概念⑷．定义s的一次循环s(1)=s[2→|s|]+s[1]；s的k次循环(k1)s(k)为s(k-1)的一次循环；s的0次循环s(0)=s。12…i…j…|s|s串：12…i…j…|s|S(1)串：IOI2003冬令营演示文稿安徽周源明确几个记号和概念⑸．如果字符串s1可以经过有限次循环得到s2，则称s1和s2是循环同构的。例如：s1和s2是循环同构的！s1=‘abcd’‘bcda’一次循环s2=‘cdab’一次循环IOI2003冬令营演示文稿安徽周源明确几个记号和概念⑹．设有两个映射f1，f2:A→A，定义f1和f2的连接f1•f2(x)=f1(f2(x))。IOI2003冬令营演示文稿安徽周源问题的数学语言表达形式给定两个长度相等的字符串，|s1|=|s2|，判断它们是否是循环同构的。IOI2003冬令营演示文稿安徽周源枚举算法易知，s1的不同的循环串最多只有|s1|个，即s1,s1(1),s1(2),…s1(|s1|-1)，所以只需要把他们一一枚举，然后分别与s2比较即可。IOI2003冬令营演示文稿安徽周源枚举算法优点：思维简单，易于实现。时间复杂度是O(N2)级（N=|s1|=|s2|）。如果N大一些，几十万，几百万……TimeLimitExceeded!IOI2003冬令营演示文稿安徽周源构造新的算法首先构造新的模型：S=s1+s1为主串，s2为模式串。如果s1和s2是循环同构的，那么s2就一定可以在S中找到匹配！IOI2003冬令营演示文稿安徽周源匹配算法：理论的下界在S中寻找s2的匹配是有很多O(N)级的算法的。本题最优算法的时空复杂度均为O(N)级。这已经是理论的下界了。IOI2003冬令营演示文稿安徽周源小结：枚举和匹配算法很容易得到的枚举算法显然不能满足大数据的要求，于是我们从算法的执行过程入手，探查到了枚举算法的实质：模式匹配。最后，通过巧妙的构造、转换模型，直接套用模式匹配算法，得到了O(N)级的算法。IOI2003冬令营演示文稿安徽周源探索新的算法但是问题是否已经完美解决了呢？KMP算法的缺点：难理解，难记忆；可扩展性不强。IOI2003冬令营演示文稿安徽周源[引例]有两列数a1,a2…an和b1,b2…bn，不记顺序，判断它们是否相同。{an}：4263{bn}：6234相同的两列数IOI2003冬令营演示文稿安徽周源[分析]由于题目要求“不记顺序”，因此每一列数的不同形式高达n!种之多！如果要一一枚举，显然是不科学的。如果两列数是相同的，那么将它们排序之后得到的数列一定也是相同的。{an}：4263{bn}：6234排序后{an}：2346{bn}：2346相同IOI2003冬令营演示文稿安徽周源小结：引例这道题虽然简单，却给了我们一个重要的启示：当某两个对象有多种表达形式，且需要判断它们在某种变化规则下是否能够达到一个相同的形式时，可以将它们都按一定规则变化成其所有表达形式中的最小者，然后只需要比较两个“最小者”是否相等即可！IOI2003冬令营演示文稿安徽周源定义：“最小表示法”设有事物集合T={t1，t2，…，tn}，映射集合F={f1，f2，…，fm}。任意f∈F均为T到T的映射，fi:T→T。如果两个事物s,t∈T，有一系列F的映射的连接fi1•fi2•…•fik(s)=t，则说s和t是F本质相同的。IOI2003冬令营演示文稿安徽周源定义：“最小表示法”其中F满足两个条件：⑴．任意t∈T，一定能在F中一系列映射的连接的作用下，仍被映射至t。即任意一个事物t∈T，它和自己是F本质相同的。⑵．任意s,t∈T，若在F的一系列映射作用下，s和t是F本质相同的。那么一定有另一系列属于F的映射作用下，t和s是F本质相同的。即“本质相同”这个概念具有自反性。即“本质相同”这个概念具有对称性。IOI2003冬令营演示文稿安徽周源定义：“最小表示法”另外，根据“本质相同”概念的定义很容易知道，“本质相同”这个概念具有传递性。即若t1和t2是F本质相同，t2和t3是F本质相同，那么一定有t1和t3是本质相同的。IOI2003冬令营演示文稿安徽周源定义：“最小表示法”给定T和F，如何判断T中两个事物s和t是否互为F本质相同呢？“最小表示法”就是可以应用于此类题目的一种思想：确立一种T中事物的大小关系根据F中的变化规则将s和t化成规定大小关系中的最小者m1和m2如果m1=m2s本质相同m1本质相同m2本质相同tm1≠m2可以证明，s和t不是本质相同IOI2003冬令营演示文稿安徽周源“最小表示法”在本题的应用在本题中，事物集合表示的是不同的字符串，映射集合则表示字符串的循环法则,“事物中的大小关系”就是字符串间的大小关系。分别求出s1和s2的最小表示比较它们是否相同最直接最简单的方法：IOI2003冬令营演示文稿安徽周源“最小表示法”在本题的应用如M(‘bbbaab’)=4设函数M(s)返回值意义为：从s的第M(s)个字符引起的s的一个循环表示是s的最小表示。若有多个值，则返回最小的一个。现在换一种思路：s=‘bbbaab’IOI2003冬令营演示文稿安徽周源“最小表示法”在本题的应用现在换一种思路：1…|s1|s1:1…|s2|s2:u:w:1…|s1||s1|+1…2*|s1|1…|s2||s2|+1…2*|s2|设u=s1+s1，w=s2+s2并设指针i,j指向u,w第一个字符IOI2003冬令营演示文稿安徽周源“最小表示法”在本题的应用u:1…M(s1)……2*|s1|w:1……M(s2)…2*|s2|ij现在换一种思路：如果s1和s2是循环同构的，那么当i,j分别指向M(s1),M(s2)时，一定可以得到u[i→i+|s1|-1]=w[j→j+|s2|-1]，迅速输出正确解。|s1||s2|IOI2003冬令营演示文稿安徽周源“最小表示法”在本题的应用现在换一种思路：同样s1和s2循环同构时，当i,j分别满足i≤M(s1),j≤M(s2)时，两指针仍有机会达到i=M(s1),j=M(s2)这个状态。问题转化成，两指针分别向后滑动比较，如果比较失败，如何正确的滑动指针，新指针i’,j’仍然满足i’≤M(s1),j’≤M(s2)IOI2003冬令营演示文稿安徽周源“最小表示法”在本题的应用设指针i,j分别向后滑动k个位置后比较失败(k≥0)，即有u[i+k]≠w[j+k]1…i………u：i+ki+k+1…|s1|…1…w：j………j+kj+k+1…|s2|…大于当i≤x≤i+k时，我们来研究s1(x-1)。x设u[i+k]w[j+k]，同理可以讨论u[i+k]w[j+k]的情况。IOI2003冬令营演示文稿安徽周源“最小表示法”在本题的应用因为u[x]在u[i]后(x-i)个位置，对应的可以找到在w[j]后(x-i)个位置的w[j+(x-i)]，1…i…x…u：i+ki+k+1…|s1|…1…w：j………j+kj+k+1…|s2|…大于j+(x-i)相等同样对应的有u[x+1]和w[j+(x+1-i)]，u[x+2]和w[j+(x+2)-i]，直到u[i+k-1]和w[j+k-1]。它们都是相等的，即有u[x→i+k-1]=w[j+(x-i)→j+k-1]。IOI2003冬令营演示文稿安徽周源“最小表示法”在本题的应用很容易就得到u[x→i+k]w[j+(x-i)→j+k]。1…i…x…u：i+ki+k+1…|s1|…1…w：j…j+(x-i)…j+kj+k+1…|s2|…大于s1(x-1)的前几个字符一定是s1的其他循环表示的前几个字符所以s1(x-1)不可能是s1的最小表示！因此M(s1)i+k，指针i滑到u[i+k+1]处仍可以保证小于等于M(s1)！IOI2003冬令营演示文稿安徽周源“最小表示法”在本题的应用同理，当u[i+k]w[j+k]的时候，可以将指针j滑到w[j+k+1]处！也就是说，两指针向后滑动比较失败以后，指向较大字符的指针向后滑动k+1个位置。下面让我们将这种方法应用于一个实例。IOI2003冬令营演示文稿安徽周源“最小表示法”在本题的应用设s1=‘babba’，s2=‘bbaba’。u=‘babbababba’w=‘bbababbaba’ij比较失败时k=1不相等因为u[i+k]w[j+k]所以移动指针jjIOI2003冬令营演示文稿安徽周源“最小表示法”在本题的应用设s1=‘babba’，s2=‘bbaba’。u=‘babbababba’w=‘bbababbaba’i不相等因为u[i+k]w[j+k]所以移动指针iji比较失败时k=0IOI2003冬令营演示文稿安徽周源“最小表示法”在本题的应用设s1=‘babba’，s2=‘bbaba’。u=‘babbababba’w=‘bbababbaba’不相等因为u[i+k]w[j+k]所以移动指针ijii比较失败时k=2IOI2003冬令营演示文稿安徽周源“最小表示法”在本题的应用设s1=‘babba’，s2=‘bbaba’。u=‘babbababba’w=‘bbababbaba’jiu[5→9]=w[3→7]！所以s1和s2是循环同构的！IOI2003冬令营演示文稿安徽周源“最小表示法”在本题的应用在这个例子中，算法正确出解。算法的具体描述和证明请同学们自行完成，这里不再赘述。IOI2003冬令营演示文稿安徽周源小结：“最小表示法”思想经过努力，我们终于找到了一个与匹配算法本质不同的线性算法。比较点匹配算法“最小表示法”思想时间复杂度O(N)级同样优秀的线性算法辅助空间记录next数组O(N)级只需要记录两个指针常数级别算法实现难懂，难记忆简洁，便于记忆可扩展性受next数组严重制约很强IOI2003冬令营演示文稿安徽周源总结“最小表示法”是判断两种事物本质是否相同的一种常见思想，它的通用性也是被人们认可的——无论是搜索中判重技术，还是判断图的同构之类复杂的问题，它都有着无可替代的作用。仔细分析可以得出，其思想精华在于引入了“序”这个概念，从而将纷繁的待处理对象化为单一的形式，便于比较。“最小表示法”思想应用判重技术判断图的同构……同构类问题单一的形式有序化IOI2003冬令营演示文稿安徽周源总结然而值得注意的是，在如今的信息学竞赛中，试题纷繁复杂，使用的算法也不再拘泥于几个经典的算法，改造经典算法或是将多种算法组合是常用的方法之一。正如本文讨论的问题，单纯的寻求字符串的最小表示显得得不偿失，但利用“最小表示法”的思想，和字符串的最小表示这个客观存在的事物，我们却找到了一个简单、优秀的算法。“最小表示法”思想应用判重技术判断图的同构……同构类问题找到更简单，更优秀的算法！与其他思想综合运用单一的形式有序化IOI2003冬令营演示文稿安徽周源总结解决实际问题时，只有深入分析，敢于创新，才能将问题化纷繁为简洁，化无序为有序。IOI2003冬令营演示文稿安徽周源谢谢大家