题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中, 则字符串一称之为字符串二的子串。
- 注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。 请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。 例如:输入两个字符串 BDCABA 和 ABCBDAB,字符串 BCBA 和 BDAB 都是是它们的最 长公共子序列,则输出它们的长度 4,并打印任意一个子序列。
事实上,最长公共子序列问题也有最优子结构性质。
记：
-
Xi=<x1,⋯,xi>即 X 序列的前 i 个字符 (1≤i≤m)(前缀)
-
Yj=<y1,⋯,yj>即 Y 序列的前 j 个字符 (1≤j≤n)(前缀)
-
假定 Z=<z1,⋯,zk>∈LCS(X , Y)
- 若 xm=yn(最后一个字符相同),则不难用反证法证明:该字符必是 X 与 Y 的任 一最长公共子序列 Z(设长度为 k)的最后一个字符,即有 zk = xm = yn 且显然有 Zk-1∈LCS(Xm-1 , Yn-1)即 Z 的前缀 Zk-1 是 Xm-1 与 Yn-1 的最长公共子序列。此 时,问题化归成求 Xm-1 与 Yn-1 的 LCS(LCS(X , Y)的长度等于 LCS(Xm-1 , Yn-1) 的长度加 1)。
- 若 xm≠yn,则亦不难用反证法证明:要么 Z∈LCS(Xm-1, Y),要么 Z∈LCS(X , Yn-1)。 由于 zk≠xm 与 zk≠yn 其中至少有一个必成立,若 zk≠xm 则有 Z∈LCS(Xm-1 , Y), 类似的,若 zk≠yn 则有 Z∈LCS(X , Yn-1)。此时,问题化归成求 Xm-1 与 Y 的 LCS 及 X 与 Yn-1 的 LCS。LCS(X , Y)的长度为:max{LCS(Xm-1 , Y)的长度, LCS(X , Yn-1) 的长度}。
最长公共子序列的结构有如下表示:
设序列 X=<x1, x2, ..., xm>和 Y=<y1, y2, ..., yn>的一个最长公共子序列 Z=<z1, z2, ..., zk>, 则:
- 若 xm=yn,则 zk=xm=yn 且 Zk-1 是 Xm-1 和 Yn-1 的最长公共子序列;
- 若 xm≠yn 且 zk≠xm ,则 Z 是 Xm-1 和 Y 的最长公共子序列;
- 若 xm≠yn 且 zk≠yn ,则 Z 是 X 和 Yn-1 的最长公共子序列。
由最长公共子序列问题的最优子结构性质可知,要找出 X=<x1, x2, ..., xm>和 Y=<y1, y2, ..., yn>的最长公共子序列,可按以下方式递归地进行:当 xm=yn 时,找出 Xm-1 和 Yn-1 的最长公 共子序列,然后在其尾部加上 xm(=yn)即可得 X 和 Y 的一个最长公共子序列。当 xm≠yn 时, 必须解两个子问题,即找出 Xm-1 和 Y 的一个最长公共子序列及 X 和 Yn-1 的一个最长公共子 序列。这两个公共子序列中较长者即为 X 和 Y 的一个最长公共子序列。
由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如,在计算 X 和 Y 的最长公共子序列时,可能要计算出 X 和 Yn-1 及 Xm-1 和 Y 的最长公共子序列。而这两个子 问题都包含一个公共子问题,即计算 Xm-1 和 Yn-1 的最长公共子序列。
与矩阵连乘积最优计算次序问题类似,我们来建立子问题的最优值的递归关系。用 c[i,j] 记录序列 Xi 和 Yj 的最长公共子序列的长度。其中 Xi=<x1, x2, ..., xi>,Yj=<y1, y2, ..., yj>。当 i=0 或 j=0 时,空序列是 Xi 和 Yj 的最长公共子序列,故 c[i,j]=0。其他情况下,由定理可建 立递归关系如下: