文档介绍：该【最长公共子串问题公开课获奖课件赛课一等奖课件 】是由【读书之乐】上传分享，文档一共【18】页，该文档可以免费在线阅读，需要了解更多关于【最长公共子串问题公开课获奖课件赛课一等奖课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。最长公共子串问题
最长公共子串问题 （Longest common substring, 简称LCS）
[问题描述]一种字符串的某个子串，就是结定的字符串再去掉几种元素(也许一种也不去掉)。
形式化地，结定字符串X=<Xl，X2，…，Xm>，和另一字符串Z＝<Zl，Z2，… ，Zk>，假如存在X的一种严格递增的下标序列<i1, i2, …, ik>，使得对所有的J = 1, 2, …, k ，有
则Z是X的子串。例如Z＝<B, C, D, B> 就是X＝＜A, B, C, B, D, A, B>的一种子串，
对应的下标序列为<2，3，5，7>。
给定三个序列 X，Y和Z，假如Z既是X的一种子串又是Y的一种子串，则称Z是X和Y的公共子串。例如X＝＜A，B，C，B，D，A，D＞，Y＝＜B，D，C，A，B，A＞。
则序列<B，C，A>，即为X和Y的一种公共子串，但不是X和Y的最长公共子串(LCS)， 由于尚有比它更长的公共子串<B，C，B，A＞。 <B，C，B，A>是X和Y的一种LCS ，字符串<B，D，A，B>也是。
[问题] 现输入两个字符串X＝<X1, X2, …, Xm>和Y＝<Y1, Y2, …, Yn>，规定出X和Y的最长公共子串。
分析
描述LCS问题最优解的构造
首先．我们给出一种字符串“前缀”的概念：
给定一种字符串X=<X1, X2, …, Xm>，对I= 0, 1, …, m，定义X的第i个前缀为
例如，假如X＝＜A，B，C，B，D，A，B＞，则
而 则为空串。
两个输入字符串X和Y的所有前缀构成了LCS问题的子问题空间。由此我们发现LCS问题的最优子构造的三个性质：
设X＝<X1, X2, …, Xm>和Y＝<Y1, Y2, …, Yn>为两个输入字符串，并设X和Y的最长公共子串为Z=<Z1, Z2, …, Zk>
性质1：假如Xm = Yn，则Zk = Xm = Yn，且
也就是说，假如两个字符串最终一位字符相等，则它们的最长公共子串的最终一位就是这个字符，并且公共子串的第k-1个前缀是两个字符串前缀的最长公共子串
分析
举例阐明：
X = <A, B, E, …, G, F>
Y= <C, D, H, …, K, F>
因X和Y的最终一位相等，则它们的最长公共子串Z的最终一位必为F，即有
Z = <……, F>的样式。并且 Z’=<……>是X’=<A, B, E, …,G> 和Y’=<C,D,H, …,K>的最长公共子串。
性质2：
也就是说，假如两个字符串最终一位不等，则它们的最长公共子串Z的最终一位不等于X的最终一位，就意味着Z是X的前缀与Y的最长公共子串。
举例阐明：
X = <A, B, E, …, G, M>
Y= <C, D, H, …, K, S>
Z= <……, F>
因X和Y最终一位不等，X和它的子串的最终一位也不等，则Z是X’=<A,B,E…,G>和Y的最长公共子串
分析-最优子构造
性质3：
也就是说，假如两个字符串最终一位不等，则它们的最长公共子串Z的最终一位不等于Y的最终一位，就意味着Z是X与Y的前缀的最长公共子串。
举例阐明：
X = <A, B, E, …, G, W>
Y= <C, D, H, …, K, I>
Z= <……, F>
因X和Y最终一位不等，Y和它的子串的最终一位也不等，则Z是X和Y’=<C,D,H, …K>的最长公共子串
由此可见，字符串X和Y的一种最长公共子串也是包含了两个字符串的前缀的一种最长公共子串，这就阐明了LCS问题具有最优子构造性质。
递归地定义LCS的值
由LCS问题的最优子构造的三个性质可知，规定X=<X1, X2, …, Xm>和Y＝<Y1, Y2, …, Yn> 的一种LCS，也许要检查如下子问题：
1．若Xm＝Yn，我们就要找出
2．假如Xm≠Yn，我们就要处理两个问题：
取两者中较长者作为X和Y的LCS。由此我们很容易看出重叠子问题的性质：为找出X和Y的一种LCS，我们也许需要找X和 的一种LCS与 和Y的一种LCS，这两个子问题都包含着找 和 的LCS的子问题。尚有许多其他子问题都具有公共子子问题。
递归地定义LCS的值
用实例来阐明上述查找过程。
设X＝＜A，B，C，B＞，Y＝＜B，D，C＞
1) X4 = B, Y3=C , X4 <> Y3，因此转而求“ X’=<A,B,C>与Y的LCS” 和 “Y’= <B,D>与X的LCS”。谁长谁就是X和Y的LCS。
2a) X=<A,B,C>, Y=<B,D,C>, X3=Y3, 因此转而求X=<A,B>与Y=<B,D>的LCS。
2b) X=<A,B,C,B>, Y=<B,D>, X4<>Y2, 因此转而求X=<A,B,C>与Y=<B,D> 和 X=<A,B,C,B>与Y=<B>的LCS。
3a) X=<A,B>, Y= <B,D>, X2<>Y2, 因此转而求<A>与<B,D> 和<A,B>与<B>的LCS。
3b1)X=<A,B,C>, Y=<B,D>, X3<>Y2, 因此转而求<A,B,C>与<B>的LCS和<A,B>与<B,D>的LCS
3b2) X=<A,B,C,B>, Y=<B>, X4=Y1, 转而求 <A,B,C>与<>的LCS。在下一次计算中，就会遇到<A,B,C>与<>。显然，一种字符串与一种空串的公共子串仍是一种空串，长度为0。因此X=<A,B,C,B>, Y=<B>的LCS为<B>，长度为1
4a)同理， <A>与<B,D> 的LCS为<>; <A,B>与<B>的LCS为<B>, 因此<A,B>与<B,D>的LCS为<B>
4b)因<A,B,C>与<B>的LCS为<B>; <A,B>与<B,D>的LCS为<B> 故<A,B,C,B>与<B,D>的LCS为<B>
5a)因此<A,B>与<B,D>的LCS为<B> 故<A,B,C>与<B,D,C>的LCS为<B,C>
6) 因<A,B,C>与<B,D,C>的LCS为<B,C>； <A,B,C,B>与<B,D>的LCS为<B> 故
<A,B,C,B>与<B,D,C>的LCS为<B,C>
递归地定义LCS的值
设C[I,J]为字符串X和Y的最长公共子串的长度。X的长度为I，Y的长度为J。若I=0或者J=0，也就是说两个字符串之一的长度为0，目前LCS的长度值也必为0。由LCS问题的最优子构造可得递归式：
Y
B
D
C
X
0
0
0
0
A
0
0
0
0
B
0
1
1
1
C
0
1
1
2
B
0
1
1
2
自底向上求LCS的值
我们看到C[I，J]由两个自变量构成，I表达X的长度，J表达Y的长度。那么选择哪一种作为阶段变量更好呢？由于两个字符串在性质上没有区别，因此选择哪一种作阶段变量都无所谓。为简单计，不妨取I作为阶段变量。
因此阶段变量k的值范围是：1<=k<=I.
阶段k表达求X的第k个前缀X’k与Y的最长公共子串。