字符串算法集合.ppt

字符串循环最小表示 樊向宇 359419163@ 问题引入 有两条环状的项链，每条项链上各有N个多种颜色的珍珠，相同颜色的珍珠，被视为相同。 问题：判断两条项链是否相同。 简单分析：由于项链是环状的，因此循环以后的项链被视为相同的，如图的两条项链就是一样的。 Problem 给定两个长度相等的字符串，|s1|=|s2|， 判断它们是否是循环同构的。 解法 可转化为以S1+S1为母串,S2为模式串的匹配问题 “最小表示法”在本题的应用 如M(‘bbbaab’)=4 设函数M(s)返回值意义为： 从s的第M(s)个字符引起的s的一个循环表示是s的最小表示。 若有多个值，则返回最小的一个。 现在换一种思路： s=‘b b b a a b’ “最小表示法”在本题的应用 现在换一种思路： 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第一个字符 “最小表示法”在本题的应用 u: 1 … M(s1) … … 2*|s1| w: 1 … … M(s2) … 2*|s2| i j 现在换一种思路： 如果s1和s2是循环同构的，那么当i,j分别指向M(s1),M(s2)时，一定可以得到u[i→i+|s1|-1]=w[j→j+|s2|-1]，迅速输出正确解。 |s1| |s2| “最小表示法”在本题的应用 现在换一种思路： 同样s1和s2循环同构时，当i,j分别满足 i≤M(s1),j≤M(s2)时， 两指针仍有机会达到i=M(s1),j=M(s2)这个状态。 问题转化成，两指针分别向后滑动比较，如果比较失败，如何正确的滑动指针，新指针i’,j’仍然满足 i’≤M(s1),j’≤M(s2) “最小表示法”在本题的应用 设指针i,j分别向后滑动k个位置后比较失败(k≥0)，即有 u[i+k]≠w[j+k] 1 … i … … … u： i+k i+k+1 … |s1|… 1 … w： j … … … j+k j+k+1 … |s2|… 大于 当i≤x≤i+k时，我们来研究s1(x-1)。 x 设u[i+k]w[j+k]，同理可以讨论u[i+k]w[j+k]的情况。 “最小表示法”在本题的应用 因为u[x]在u[i]后(x-i)个位置， 对应的可以找到在w[j]后(x-i)个位置的w[j+(x-i)]， 1 … i … x … u： i+k i+k+1 … |s1|… 1 … w： j … … … j+k j+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]。 “最小表示法”在本题的应用 很容易就得到u[x→i+k]w[j+(x-i)→j+k]。 1 … i … x … u： i+k i+k+1 … |s1|… 1 … w： j … j+(x-i) … j+k j+k+1 … |s2|… 大于 s1(x-1)的前几个字符 一定是s1的其他循环表示的前几个字符 所以s1(x-1)不可能是s1的最小表示！ 因此M(s1)i+k， 指针i滑到u[i+k+1]处仍可以保证小于等于M(s1)！ “最小表示法”在本题的应用 同理，当u[i+k]w[j+k]的时候，可以将指针j滑到w[j+k+1]处！ 也就是说，两指针向后滑动比较失败以后， 指向较大字符的指针向后滑动k+1个位置。 下面让我们将这种方法应用于一个实例。 “最小表示法”在本题的应用 设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