LCS
问题描述: 在两个给定的序列中, 找出最长的公共子序列(Largest Common Sequence), 比如LCS(ABDCAC, BAACDC) = BCC(解不唯一);
分析
最优子结构
这个问题是具有最优子结构的特性的, 也就是说最后一阶段的那个大的结构, 是包含了前面的最优子结构的. 在LCS问题中, 最后最大的结构可以看成是A[m-1]和B[n-1]两个子序列, 再加上最后的a, b两个元素. 此时我们应该已经得到了LCS(A[m-1], B[n-1]), 那么最后阶段我们的决策就是要不要再延长这个子序列;递归式
LCS(A[m], B[n]) =
if a == b,
LCS(A[m-1], B[n-1]) + a
if a!=b
max { LCS(A[m-1], {B[n-1]+b} ), LCS( {A[m-1]+a}, B[n-1]) }
写得更简洁一些:
c(i, j) = //Common, 返回值是LCS有多少个char
(1) c(i-1, j-1) +1 , A[i] == B[j]
(2) max{c(i-1, j), c(i, j-1)} , A[i] != A[j]
(3) 0 , 边界条件i==0 || j==0 即出现有一条序列是长度为0的, 那么肯定公共序列长度为0;自底向上计算的算法
//输入: X, Y为两条序列
LCS(X[1~m], Y[1~n])
//初始化
let c[1~m][1~n] and rec[1~m][1~n] be new tables
for (i = 0~m)
c[i][0] = 0
for (j = 0~n)
c[0][j] = 0
//开始计算
for (i= 1~m)
for (j= 1~n)
if (X[i] == Y[j])
c[i][j] = c[i-1][j-1] + 1
rec[i][j] = 1 (↖️)
else if (c[i-1][j] >= c[i][j-1])
c[i][j] = c[i-1][j]
rec[i][j] = 0 (↑)
else
c[i][j] = c[i][j-1]
rec[i][j] = 2 (←)
return c and rec
Print-LCS(rec[1~m][1~n], X[1~m], i, j)
if i==0 or j==0
return
if rec[i, j] == 1 (↖️)
Print-LCS(rec, X, i-1, j-1)
printf (X[i]) //因为讲求顺序, 因此从后往前找的时候, 先发现的后打印, 才能形成正确的顺序;
if rec[i, j] == 0 (↑)
Print-LCS(rec, X, i-1, j)
else (←)
Print-LCS(rec, X, i, j-1)
