algorithm - 转到 : longest common subsequence to print result array

Question

我已经实现了最长公共(public)子序列算法并得到了最长的正确答案，但无法找出打印出最长公共(public)子序列的组成部分的方法。

也就是说，我成功获取了最长公共(public)子序列数组的长度，但我想打印出最长的子序列。

此代码的 Playground 就在这里

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”的内容

提前致谢。

Answer 1

编辑:看来我是仓促回答了这个问题。在维基百科页面上 Longest Common Subsequnce一旦计算出 LCS，他们就会给出打印出 LCS 的伪代码。我会在有空的时候尽快在 go up 中添加一个实现。

旧的无效答案

一旦您将某个角色注册为子序列的一部分，您就会忘记从该角色继续前进。

下面的代码应该可以工作。查看 fmt.Printf("%c", srt1[i]) 行之后的两行。

playground link

/*
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
}