资源描述：
《国家集训队2003论文集_周源》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、浅析“最小表示法”思想在字符串循环同构问题中的应用安徽省芜湖市第一中学周源前言“最小表示法”比起动态规划、贪心等思想，在当今竞赛中似乎并不是很常见。但是在解决判断“同构”一类问题中却起着重要的作用。本文即将讨论字符串中的同构问题，如何巧妙地运用最小表示法来解题呢，让我们继续一起思考吧。问题引入有两条环状的项链，每条项链上各有N个多种颜色的珍珠，相同颜色的珍珠，被视为相同。问题：判断两条项链是否相同。简单分析：由于项链是环状的，因此循环以后的项链被视为相同的，如图的两条项链就是一样的。明确几个记号和概念⑴．
2、s
3、=length(s)，即s的长度。1…i…j…
4、s
5、s串：⑵．s
6、[i]为s的第i个字符。⑶．s[i→j]=copy(s,i,j-i+1)。这里1≤i≤j≤
7、s
8、。s[i→j]明确几个记号和概念⑷．定义s的一次循环s(1)=s[2→
9、s
10、]+s[1]；s的k次循环(k>1)s(k)为s(k-1)的一次循环；s的0次循环s(0)=s。12…i…j…
11、s
12、s串：12…i…j…
13、s
14、S(1)串：明确几个记号和概念⑸．如果字符串s1可以经过有限次循环得到s2，则称s1和s2是循环同构的。例如：s1和s2是循环同构的！s1=‘abcd’‘bcda’一次循环s2=‘cdab’一次循环明确几个记号和概念⑹．设有两个映射f1，f2:A→A，定义f1和f2
15、的连接f1•f2(x)=f1(f2(x))。问题的数学语言表达形式给定两个长度相等的字符串，
16、s1
17、=
18、s2
19、，判断它们是否是循环同构的。枚举算法易知，s1的不同的循环串最多只有
20、s1
21、个，即s1,s1(1),s1(2),…s1(
22、s1
23、-1)，所以只需要把他们一一枚举，然后分别与s2比较即可。枚举算法优点：思维简单，易于实现。时间复杂度是O(N2)级（N=
24、s1
25、=
26、s2
27、）。如果N大一些，几十万，几百万……TimeLimitExceeded!构造新的算法首先构造新的模型：S=s1+s1为主串，s2为模式串。如果s1和s2是循环同构的，那么s2就一定可以在S中找到匹配！匹
28、配算法：理论的下界在S中寻找s2的匹配是有很多O(N)级的算法的。本题最优算法的时空复杂度均为O(N)级。这已经是理论的下界了。小结：枚举和匹配算法很容易得到的枚举算法显然不能满足大数据的要求，于是我们从算法的执行过程入手，探查到了枚举算法的实质：模式匹配。最后，通过巧妙的构造、转换模型，直接套用模式匹配算法，得到了O(N)级的算法。探索新的算法但是问题是否已经完美解决了呢？KMP算法的缺点：难理解，难记忆；可扩展性不强。[引例]有两列数a1,a2…an和b1,b2…bn，不记顺序，判断它们是否相同。{an}：4263{bn}：6234相同的两列数[分析]由于题目要求“不记
29、顺序”，因此每一列数的不同形式高达n!种之多！如果要一一枚举，显然是不科学的。如果两列数是相同的，那么将它们排序之后得到的数列一定也是相同的。{an}：4263{bn}：6234排序后{an}：2346{bn}：2346相同小结：引例这道题虽然简单，却给了我们一个重要的启示：当某两个对象有多种表达形式，且需要判断它们在某种变化规则下是否能够达到一个相同的形式时，可以将它们都按一定规则变化成其所有表达形式中的最小者，然后只需要比较两个“最小者”是否相等即可！定义：“最小表示法”设有事物集合T={t1，t2，…，tn}，映射集合F={f1，f2，…，fm}。任意f∈F均为T到T
30、的映射，fi:T→T。如果两个事物s,t∈T，有一系列F的映射的连接fi1•fi2•…•fik(s)=t，则说s和t是F本质相同的。定义：“最小表示法”其中F满足两个条件：⑴．任意t∈T，一定能在F中一系列映射的连接的作用下，仍被映射至t。即任意一个事物t∈T，它和自己是F本质相同的。⑵．任意s,t∈T，若在F的一系列映射作用下，s和t是F本质相同的。那么一定有另一系列属于F的映射作用下，t和s是F本质相同的。即“本质相同”这个概念具有自反性。即“本质相同”这个概念具有对称性。定义：“最小表示法”另外，根据“本质相同”概念的定义很容易知道，“本质相同”这个概念具有传递性。即
31、若t1和t2是F本质相同，t2和t3是F本质相同，那么一定有t1和t3是本质相同的。定义：“最小表示法”给定T和F，如何判断T中两个事物s和t是否互为F本质相同呢？“最小表示法”就是可以应用于此类题目的一种思想：确立一种T中事物的大小关系根据F中的变化规则将s和t化成规定大小关系中的最小者m1和m2如果m1=m2s本质相同m1本质相同m2本质相同tm1≠m2可以证明，s和t不是本质相同“最小表示法”在本题的应用在本题中，事物集合表示的是不同的字符串，映射集合则表示字符串的循环法则,“事物中的大小关系”就是字符串间的
