1 回答

TA貢獻(xiàn)1824條經(jīng)驗(yàn) 獲得超8個(gè)贊
似乎我在回答這個(gè)問(wèn)題時(shí)跳了起來(lái)。在最長(zhǎng)公共子序列的維基百科頁(yè)面上,他們給出了計(jì)算出 LCS 后打印出 LCS 的偽代碼。只要我有時(shí)間,我就會(huì)在 go up here 中放置一個(gè)實(shí)現(xiàn)。
舊的無(wú)效答案
一旦將角色注冊(cè)為子序列的一部分,您就會(huì)忘記從角色移動(dòng)。
下面的代碼應(yīng)該可以工作。查看該行之后的兩fmt.Printf("%c", srt1[i])行。
游樂(lè)場(chǎng)鏈接
/*
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 關(guān)注
- 280 瀏覽
添加回答
舉報(bào)