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

編集：これに答えることに銃を飛ばしたようです。ウィキペディアのLongest Common Subsequenceのページでは、計算後に LCS を出力するための疑似コードが提供されています。時間ができ次第、ここに実装します。

古い無効な回答

キャラクターをサブシーケンスの一部として登録すると、そのキャラクターから移動するのを忘れています。

以下のコードは機能するはずです。行の直後の 2 行を見てください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 に答える