0

私のコードは LCS の長さを計算するために機能しますが、次のリンクで LCS を読み取るために同じコードを適用します。

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

しかし、一部の文字列が欠落しています。私が欠けているものを教えていただけますか？

Google Playground リンク: http://play.golang.org/p/qnIWQqzAf5

func Back(table [][]int, str1, str2 string, i, j int) string {
  if i == 0 || j == 0 {
    return ""
  } else if str1[i] == str2[j] {
    return Back(table, str1, str2, i-1, j-1) + string(str1[i])
  } else {
    if table[i][j-1] > table[i-1][j] {
      return Back(table, str1, str2, i, j-1)
    } else {
      return Back(table, str1, str2, i-1, j)
    }
  }
}

前もって感謝します。

4

1 に答える 1

2

私が思うに問題はあなたの索引付けにあります。0-から文字列にインデックスを付ける場合len-1、テーブルには文字列の長さよりも 1 大きい行と列の数が必要です。LCSの長さを計算するときはそれを考慮しているようですが、LCSを返すときは考慮していません。あなたのiとjは、文字列のインデックスを正しく表していますが、テーブルのインデックスは 1 より大きい必要がありますi/j。str1[0]したがって、とstr2[0]が有効な文字であるため、0 をチェックする基本条件は間違っています。

したがって、コードは次のようになります。

func Back(table [][]int, str1, str2 string, i, j int) string {
  if i == -1 || j == -1 {
    return ""
  } else if str1[i] == str2[j] {
    return Back(table, str1, str2, i-1, j-1) + string(str1[i])
  } else {
    if table[i+1][j] > table[i][j+1] {
      return Back(table, str1, str2, i, j-1)
    } else {
      return Back(table, str1, str2, i-1, j)
    }
  }
}

ライブコードはこちら

于 2013-11-22T23:42:52.317 に答える