2

我已经实现了最长公共子序列算法并获得了最长的正确答案，但无法弄清楚如何打印出构成最长公共子序列的内容。

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

这段代码的操场在这里

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

提前致谢。

4

1 回答 1

0

编辑：似乎我在回答这个问题时跳了枪。在最长公共子序列的维基百科页面上，他们给出了计算出 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
}
于 2013-11-22T14:38:00.497 回答