我已經實現了最長公共子序列算法并獲得了最長的正確答案，但無法弄清楚打印出最長公共子序列的組成部分的方法。也就是說，我成功獲得了最長公共子序列數組的長度，但我想打印出最長的子序列。此代碼的游樂場在這里http://play.golang.org/p/0sKb_OARnf/*X = BDCABAY = ABCBDAB => Longest Comman Subsequence is B C BDynamic Programming method : O ( n )*/package mainimport "fmt"func Max(more ...int) int { max_num := more[0] for _, elem := range more { if max_num < elem { max_num = elem } } return max_num}func Longest(str1, str2 string) int { len1 := len(str1) len2 := len(str2) //in C++, //int tab[m + 1][n + 1]; //tab := make([][100]int, len1+1) tab := make([][]int, len1+1) for i := range tab { tab[i] = make([]int, len2+1) } i, j := 0, 0 for i = 0; i <= len1; i++ { for j = 0; j <= len2; j++ { if i == 0 || j == 0 { tab[i][j] = 0 } else if str1[i-1] == str2[j-1] { tab[i][j] = tab[i-1][j-1] + 1 if i < len1 { fmt.Printf("%c", str1[i]) } } else { tab[i][j] = Max(tab[i-1][j], tab[i][j-1]) } } } fmt.Println() return tab[len1][len2]}func main() { str1 := "AGGTABTABTABTAB" str2 := "GXTXAYBTABTABTAB" fmt.Println(Longest(str1, str2)) //Actual Longest Common Subsequence: GTABTABTABTAB //GGGGGTAAAABBBBTTTTAAAABBBBTTTTAAAABBBBTTTTAAAABBBB //13 str3 := "AGGTABGHSRCBYJSVDWFVDVSBCBVDWFDWVV" str4 := "GXTXAYBRGDVCBDVCCXVXCWQRVCBDJXCVQSQQ" fmt.Println(Longest(str3, str4)) //Actual Longest Common Subsequence: ? //GGGTTABGGGHHRCCBBBBBBYYYJSVDDDDDWWWFDDDDDVVVSSSSSBCCCBBBBBBVVVDDDDDWWWFWWWVVVVVV //14}當我嘗試在選項卡更新時打印出子序列時，結果是重復的。我想為 str1 和 str2 打印出類似“GTABTABTABTAB”的內容
1 回答
有只小跳蛙
TA貢獻1824條經驗 獲得超8個贊
似乎我在回答這個問題時跳了起來。在最長公共子序列的維基百科頁面上，他們給出了計算出 LCS 后打印出 LCS 的偽代碼。只要我有時間，我就會在 go up here 中放置一個實現。
舊的無效答案
一旦將角色注冊為子序列的一部分，您就會忘記從角色移動。
下面的代碼應該可以工作。查看該行之后的兩fmt.Printf("%c", srt1[i])行。
游樂場鏈接
/*
X = BDCABA
Y = ABCBDAB => Longest Comman Subsequence is B C B
Dynamic Programming method : O ( n )
*/
package main
import "fmt"
func Max(more ...int) int {
max_num := more[0]
for _, elem := range more {
if max_num < elem {
max_num = elem
}
}
return max_num
}
func Longest(str1, str2 string) int {
len1 := len(str1)
len2 := len(str2)
//in C++,
//int tab[m + 1][n + 1];
//tab := make([][100]int, len1+1)
tab := make([][]int, len1+1)
for i := range tab {
tab[i] = make([]int, len2+1)
}
i, j := 0, 0
for i = 0; i <= len1; i++ {
for j = 0; j <= len2; j++ {
if i == 0 || j == 0 {
tab[i][j] = 0
} else if str1[i-1] == str2[j-1] {
tab[i][j] = tab[i-1][j-1] + 1
if i < len1 {
fmt.Printf("%c", str1[i])
//Move on the the next character in both sequences
i++
j++
}
} else {
tab[i][j] = Max(tab[i-1][j], tab[i][j-1])
}
}
}
fmt.Println()
return tab[len1][len2]
}
func main() {
str1 := "AGGTABTABTABTAB"
str2 := "GXTXAYBTABTABTAB"
fmt.Println(Longest(str1, str2))
//Actual Longest Common Subsequence: GTABTABTABTAB
//GGGGGTAAAABBBBTTTTAAAABBBBTTTTAAAABBBBTTTTAAAABBBB
//13
str3 := "AGGTABGHSRCBYJSVDWFVDVSBCBVDWFDWVV"
str4 := "GXTXAYBRGDVCBDVCCXVXCWQRVCBDJXCVQSQQ"
fmt.Println(Longest(str3, str4))
//Actual Longest Common Subsequence: ?
//GGGTTABGGGHHRCCBBBBBBYYYJSVDDDDDWWWFDDDDDVVVSSSSSBCCCBBBBBBVVVDDDDDWWWFWWWVVVVVV
//14
}
- 1 回答
- 0 關注
- 290 瀏覽
添加回答
舉報
0/150
提交
取消