Go : longest common subsequence to print result array

Question

I have implemented Longest Common Subsequence algorithm and getting the right answer for longest but cannot figure out the way to print out what makes up the longest common subsequence.

That is, I succeeded to get the length of longest commond subsequence array but I want to print out the longest subsequence.

The Playground for this code is here

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
}

When I try to print out the subsequence when the tab gets updates, the outcome is duplicate. I want to print out something like "GTABTABTABTAB" for the str1 and str2

Thanks in advance.

Answer 1

EDIT: It seems that I jumped the gun on answering this. On the Wikipedia page for Longest Common Subsequnce they give the pseudocode for printing out the LCS once it has been calculated. I'll put an implementation in go up here as soon as I have time for it.

Old invalid answer

You are forgetting to move along from a character once you have registered it as part of the subsequence.

The code below should work. Look at the two lines right after the fmt.Printf("%c", srt1[i]) line.

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
}