[最小表示法].ppt

“最小表示法”在本题的应用 设s1=‘babba’，s2=‘bbaba’。 u=‘b a b b a b a b b a’ w=‘b b a b a b b a b a’ i j 比较失败时k=1 不相等 因为u[i+k]w[j+k] 所以移动指针j j “最小表示法”在本题的应用 设s1=‘babba’，s2=‘bbaba’。 u=‘b a b b a b a b b a’ w=‘b b a b a b b a b a’ i 不相等 因为u[i+k]w[j+k] 所以移动指针i j i 比较失败时k=0 “最小表示法”在本题的应用 设s1=‘babba’，s2=‘bbaba’。 u=‘b a b b a b a b b a’ w=‘b b a b a b b a b a’ 不相等 因为u[i+k]w[j+k] 所以移动指针i j i i 比较失败时k=2 “最小表示法”在本题的应用 设s1=‘babba’，s2=‘bbaba’。 u=‘b a b b a b a b b a’ w=‘b b a b a b b a b a’ j i u[5→9]=w[3→7]！ 所以s1和s2是循环同构的！ 求一个字符串的最小表示 下面是求一个字符串的最小表示的方法： 首先i=1，j=2， 若a[i+k]a[j+k],显然从i到i+k都不会是最小表示，从I到j-1也不会是最小表示，所以当i+k+1小于j时，i就变成j，否则变成i+k+1，而无论如何，j为i+1； 若a[i+k]a[j+k],显然，j直接变成j+k+1； 求一个字符串的最小表示 直到j=n。 在上述步骤中，始终保持了ij,这样就不会出现i=j而直接停止的情况。实际上，对于长度为n的字符串的n种同构，上述方法是都判断了的，只是，对于不满足的就直接跳过了。这类似于用较人体法国优解去推更优解，直到推出最优解。那么，什么情况下， “最小表示法”在本题的应用 在这个例子中，算法正确出解。 算法的具体描述和证明请同学们自行完成，这里不再赘述。 小结：“最小表示法”思想 经过努力，我们终于找到了一个与匹配算法本质不同的线性算法。 比较点 匹配算法 “最小表示法”思想 时间复杂度 O(N)级 同样优秀的线性算法 辅助空间 记录next数组 O(N)级 只需要记录两个指针 常数级别 算法实现 难懂，难记忆 简洁，便于记忆 可扩展性 受next数组严重制约 很强 总结 “最小表示法”是判断两种事物本质是否相同的一种常见思想，它的通用性也是被人们认可的——无论是有哪些信誉好的足球投注网站中判重技术，还是判断图的同构之类复杂的问题，它都有着无可替代的作用。仔细分析可以得出，其思想精华在于引入了“序”这个概念，从而将纷繁的待处理对象化为单一的形式，便于比较。 “最小表示法” 思想 应用 判重技术 判断图的同构 …… 同构类问题 单一的形式 有序化 总结 然而值得注意的是，在如今的信息学竞赛中，试题纷繁复杂，使用的算法也不再拘泥于几个经典的算法，改造经典算法或是将多种算法组合是常用的方法之一。正如本文讨论的问题，单纯的寻求字符串的最小表示显得得不偿失，但利用“最小表示法”的思想，和字符串的最小表示这个客观存在的事物，我们却找到了一个简单、优秀的算法。 “最小表示法” 思想 应用 判重技术 判断图的同构 …… 同构类问题 找到更简单，更优秀的算法！ 与其他思想综合运用 单一的形式 有序化 总结 解决实际问题时，只有深入分析，敢于创新，才能将问题 化纷繁为简洁， 化无序为有序。 谢谢大家 * IOI2003冬令营演示文稿 安徽　周源 IOI2003冬令营演示文稿 安徽　周源 浅析“最小表示法”思想在字符串循环同构问题中的应用 安徽省芜湖市第一中学 周 源 前言 “最小表示法”比起动态规划、贪心等思想，在当今竞赛中似乎并不是很常见。但是在解决判断“同构”一类问题中却起着重要的作用。 本文即将讨论字符串中的同构问题，如何巧妙地运用最小表示法来解题呢，让我们继续一起思考吧。 问题引入 有两条环状的项链，每条项链上各有N个多种颜色的珍珠，相同颜色的珍珠，被视为相同。 问题：判断两条项链是否相同。 简单分析：由于项链是环状的，因此循环以后的项链被视为相同的，如图的两条项链就是一样的。 明确几个记号和概念 ⑴．|s|=length(s)，即s的长度。 1 … i … j …