Go：打印结果数组的最长公共子序列
我已经实现了最长公共子序列算法并获得了最长的正确答案，但无法弄清楚打印出最长公共子序列的组成部分的方法。
也就是说，我成功获得了最长公共子序列数组的长度，但我想打印出最长的子序列。
此代码的游乐场在这里
http://play.golang.org/p/0sKb_OARnf
/*
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])
}
} 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回答
-
有只小跳蛙
似乎我在回答这个问题时跳了起来。在最长公共子序列的维基百科页面上，他们给出了计算出 LCS 后打印出 LCS 的伪代码。只要我有时间，我就会在 go up here 中放置一个实现。旧的无效答案一旦将角色注册为子序列的一部分，您就会忘记从角色移动。下面的代码应该可以工作。查看该行之后的两fmt.Printf("%c", srt1[i])行。游乐场链接/*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]) //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}
随时随地看视频慕课网APP
相关分类
Go