周源(最小表示法).ppt

1、“最小表示法”思想在字符串循环同体问题中的应用，安徽省芜湖市第一中学、周源、序言、“最小表示法”比动态规划、贪婪等思想，在当前竞争中似乎不太好。 但是在解决、判断“同体”这个问题上发挥着重要的作用。 本文讨论了字符串中的同体问题，一起考虑如何巧妙地使用最小表现法来解决问题。 问题被引入，有两条环状项链，每条项链有n色以上的珍珠，同一颜色的珍珠被认为是相同的。 问题：判断两条项链是否相同。 简单的分析：项链是环状的，所以循环后的项链被视为相同，如图所示的两条项链是相同的。 明确几个符号和概念，|s|=length(s )，即s的长度。 si是s的第I个字母。 复制(s，I，j-i 1)。 此处为

2、1 i j |s|。 明确一些符号和概念，s的一次循环s(1)=s2|s| s1； s的k个周期(k1)s(k )是s(k-1 )的一个周期，即s的0个周期s(0)=s。1、S(1)列：几个符号和概念，如果字符串s1可以经过有限次循环获得s2，则s1和s2称为循环是同系数。 例如： s1和s2是由犀牛喀呖声构成的！ 另外，s1=a b c d，一些符号和概念被澄清，提供了两个图f1、f2:AA，并定义了f1和f2之间的连接f1f2(x)=f1(f2(x ) )。问题的数学语言表示形式，给出长度相等的两个字符串，|s1|=|s2|，它们通过循环知更鸟来判断有木有。 为了便于理解，枚举算法，s1的

3、不同循环列最多只有|s1|个，即s1、s1(1)、s1(2)、s1(|s1|-1 )，所以将它们一一列举，分别与s2进行比较即可。 枚举算法，优点：思维简单，容易实现。 时间复杂度是O(N2)级(N=|s1|=|s2| )。 超时限执行！ 建构新算法，首先建构新模型： S=s1 s1为主列，s2为模式列。 当s1和s2为循环知更鸟时，s2一定能够在s处找到匹配！ 匹配算法：理论的下限，在s中寻找s2的匹配的是O(N )级的算法较多。 本问题最佳算法的时空复杂度都是O(N )级。 这已经是理论的下限了。 总结：枚举和匹配算法，简单易得的枚举算法显然不能满足大数据的要求，所以我们从算法的执行过程中

4、发现了枚举算法的本质：模式匹配。 最后，通过巧妙的构造、转换模型，直接应用模式匹配算法得到了O(N )级的算法。 在寻找新的算法，问题完全解决了吗？ KMP算法的缺点：难以理解，难以记忆的可扩展性低。 引用例有两个列数a1、a2an和b1、b2bn，不记得顺序，要判断它们是否相同。 同样的2列数、分析、主题被要求“不记得顺序”，因此1列数的差异高达n！ 种类很多！ 一一列举的话，显然是不科学的。 如果2个列数相同，那么排列它们得到的列也一定相同。 重新排序后，同样的，总结：引用例，这个问题很简单，但给了我们重要的提示：如果有两个对象有多种表现形式，需要判断它们在某种变化规则下是否能达到同一形式

5、，那么就把它们以一定的规则传递给所有表现形式中的最小者比较两个“最小者”是否相等即可的定义：“最小表现法”有事物集合T=t1、t2、tn、映射集合F=f1、f2、fm。 两个fF都是从t到t的映射，是fi:TT。 如果有两个事物s、t、一系列f的映射，fi1fi2fik(s)=t，那么s和t本质上是相同的。 的双曲馀弦值。 在“最小表现法”中，f满足两个条件。 任何tT都一定是通过f中的一系列映射连接映射到t的。 也就是说，任何事物tT本质上与自各儿为f的事实相同。 任意s、tT和f的一系列映射中，s和t基本相同。 t和s根据f的映射，本质上一定是一样的。 “本质上相同”的概念是否定自己的。

6、“本质上相同”的概念具有对称性。定义“最小表现法”，并且从“本质相同”的概念的定义容易传达“本质相同”的概念。 如果t1和t2的f的本质相同，t2和t3的f的本质相同，那么t1和t3一定是相同的。 定义“最小表示法”，给出t和f，t中的两个事物s和t相互用f的本质来判断有木有如何？ “最小表示法”是能够适用于这样的主题的思想之一，确立t中的事物的大小关系，根据f中的变化规则，使s和t变化为规定的大小关系中的最小值m1和m2，m1=m2、s、m1m2，则s和t本质上不相同在本题中，事物集合表示不同的字符串，映射集合表示字符串的循环规则，“事物中的大小关系”是字符串间的大小关系。 分别求s1和s2

7、的最小表现是否相同，最直接且简单的方法：“最小表现法”在主题上的应用，如，m(bbbbbbaab)=4那样，将函数M(s )的返还值的意思设为s的第M(s )个字符的s的1个循环表现为s的最小表现。 如果有多个值，则返回最小的值。 现在，改变思维方法： s=b b b a a b，“最小表现法”在本题上的应用，现在改变思维方法： u:w:u=s1，w=s2，指针I，j指u，w的第一个字符，“最小表现法”在本题上的应用，现在改变思维方法： s1和s2 指向M(s2)时，必定得到uii |s1|-1=wjj |s2|-1的“最小表现法”在主题上的应用是：当相同的s1和s2在相同的结构中循环时，当I、j分别满足iM(s1)、jM(s2)时问题