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

浅析“最小表示法”思想

在字符串循环同构问题中的应用

安徽省芜湖市第一中学

周源

前言

“最小表示法”比起动态规划、贪心等思想，在当今竞赛中似乎并不是很常见。但是在解决判断“同构”一类问题中却起着重要的作用。

本文即将讨论字符串中的同构问题，如何巧妙地运用最小表示法来解题呢，让我们继续一起思考吧。

问题引入

有两条环状的项链，每条项链上各有N个多种颜色的珍珠，相同颜色的珍珠，被视为相同。

问题：判断两条项链是否相同。

简单分析：由于项链是环状的，因此循环以后的项链被视为相同的，如图的两条项链就是一样的。

明确几个记号和概念

⑴．|s|=length(s)，即s的长度。

⑵．s[i]为s的第i个字符。

⑶．s[i→j]=copy(s,i,j-i+1)。

这里1≤i≤j≤|s|。

明确几个记号和概念

⑷．定义s的一次循环s(1)=s[2→|s|]+s[1]；

s的k次循环(k1)s(k)为s(k-1)的一次循环；

s的0次循环s(0)=s。

1

S(1)串：

明确几个记号和概念

⑸．如果字符串s1可以经过有限次循环得到s2，则称s1和s2是循环同构的。例如：

s1和

s2

是循

环同

构的

！

s1=‘abcd’

明确几个记号和概念

⑹．设有两个映射f1，f2:A→A，

定义f1和f2的连接f1•f2(x)=f1(f2(x))。

问题的数学语言表达形式

给定两个长度相等的字符串，|s1|=|s2|，

判断它们是否是循环同构的。

枚举算法

易知，s1的不同的循环串最多只有|s1|个，

即s1,s1(1),s1(2),…s1(|s1|-1)，

所以只需要把他们一一枚举，

然后分别与s2比较即可。

枚举算法

优点：思维简单，易于实现。

时间复杂度是O(N2)级（N=|s1|=|s2|）。

TimeLimitExceeded!

构造新的算法

首先构造新的模型：

S=s1+s1为主串，s2为模式串。

如果s1和s2是循环同构的，

那么s2就一定可以在S中找到匹配！

匹配算法：理论的下界

在S中寻找s2的匹配是有很多O(N)级的算法的。

本题最优算法的时空复杂度均为O(N)级。

这已经是理论的下界了。

小结：枚举和匹配算法

很容易得到的枚举算法显然不能满足大数据的要求，

于是我们从算法的执行过程入手，

探查到了枚举算法的实质：模式匹配。

最后，通过巧妙的构造、转换模型，

直接套用模式匹配算法，得到了O(N)级的算法。

探索新的算法

但是问题是否已经完美解决了呢？

KMP算法的缺点：

难理解，难记忆；

可扩展性不强。

[引例]

有两列数a1,a2…an和b1,b2…bn，不记顺序，判断它们是否相同。

相同的两列数

[分析]

由于题目要求“不记顺序”，因此每一列数的不同形式高达n!种之多！

如果要一一枚举，显然是不科学的。

如果两列数是相同的，那么将它们排序之后得到的数列一定也是相同的。

排序后

相同

小结：引例

这道题虽然简单，却给了我们一个重要的启示：当某两个对象有多种表达形式，且需要判断它们在某种变化规则下是否能够达到一个相同的形式时，可以将它们都按一定规则变化成其所有表达形式中的最小者，然后只需要比较两个“最小者”是否相等即可！

定义：“最小表示法”

设有事物集合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本质相同的。

定义：“最小表示法”

其中F满足两个条件：

⑴．任意t∈T，一定能在F中一系列映射的连接的作用下，仍被映射至t。即任意一个事物t∈T，它和自己是F本质相同的。

⑵．任意s,t∈T，若在F的一系列映射作用下，s和t是F本质相同的。那么一定有另一系列属于F的映射作用下，t和s是F本质相同的。

即“本质相同”这个概念具有自反性。

即“本质相同”这个概念具有对称性。

定义：“最小表示法”

另外，根据“本质相同”概念的定义很容易知道，“本质相同”这个概念具有传递性。

即若t1和t2是F本质相同，t2和t3是F本质相同，那么一定有t1和t3是本质相同的。

定义：“最小表示法”

给定T和F，如何判断T中两个事物s和t是否互为F本质相同呢？

“最小表示法”就是可以应用于此类题目的一种思想：