如何显示两个子串的最长公共子串的所有子串我知道计算 lcs 长度的 dp 方法但是如何显示 lcs 的所有这些 lcs 代码
function LCSLength(X[1..m], Y[1..n])
C = array(0..m, 0..n)
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
else
C[i,j] := max(C[i,j-1], C[i-1,j])
return C[m,n]
我在网上找不到一篇关于如何找到所有 lcs 的好文章
字符串 1=abcabcaa 字符串 2=acbacba
所有 lcs
ababa abaca abcba
我已经知道计算 lcs 的 dp 方法,任何帮助将不胜感激
我在维基上找到了这个
function backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j)
if i = 0 or j = 0
return {""}
else if X[i] = Y[j]
return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)}
else
R := {}
if C[i,j-1] ≥ C[i-1,j]
R := backtrackAll(C, X, Y, i, j-1)
if C[i-1,j] ≥ C[i,j-1]
R := R ∪ backtrackAll(C, X, Y, i-1, j)
return R
但我很难理解它