1

2 つの部分文字列の最長の共通部分文字列のすべての部分文字列を表示する方法 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

アババ アバカ abcba アカバ アカカ acbaa acbca

私は既に 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

しかし、それを理解するのに苦労しています

4

3 に答える 3

-1

各 c[i,j] エントリは、c[i-1,j-1]、c[i-1,j]、および c[i,j-1] の 3 つの c テーブル エントリのみに依存します。c[i,j] の値が与えられると、これら 3 つの値のどれが c[i,j] の計算に使用されたかを O(1) 時間で判断できます。前の 3 つのポイントに複数の可能な値がある場合、つまり、それらが同じであり、同じポイントで最高である場合、異なる値が可能です。次に、それらのそれぞれを考慮する必要があります。

于 2013-08-29T04:21:32.413 に答える