Go：打印结果数组的最长公共子序列

Question

我已经实现了最长公共子序列算法并获得了最长的正确答案，但无法弄清楚打印出最长公共子序列的组成部分的方法。也就是说，我成功获得了最长公共子序列数组的长度，但我想打印出最长的子序列。此代码的游乐场在这里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”的内容

Answer 1

似乎我在回答这个问题时跳了起来。在最长公共子序列的维基百科页面上，他们给出了计算出 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

}