Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>EDIT: It seems that I jumped the gun on answering this. On the Wikipedia page for <a href="http://en.wikipedia.org/wiki/Longest_common_subsequence_problem" rel="nofollow">Longest Common Subsequnce</a> 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. </p> <h3>Old invalid answer</h3> <p>You are forgetting to move along from a character once you have registered it as part of the subsequence. </p> <p>The code below should work. Look at the two lines right after the <code>fmt.Printf("%c", srt1[i])</code> line.</p> <p><a href="http://play.golang.org/p/Ng2G0g9qhN" rel="nofollow">playground link</a></p> <pre><code>/* X = BDCABA Y = ABCBDAB =&gt; 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 &lt; 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 &lt;= len1; i++ { for j = 0; j &lt;= 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 &lt; 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 } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POGo : longest common subsequence to print result array
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USyumaikas
    1. USyumaikas
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POGo : longest common subsequence to print result array
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. COThanks a lot! But It is not calculating the Longest Common Subsequence anymore then. The output is 0 and 1. And the second output is not the LCS
      singulars
      1. PO
      1. This table or related slice is empty.
    2. COI responded before fully understanding the problem. Take a look at the wikipedia article on LCS. They have an algorithm there that reads out the LCS by backtracking over the table produced by finding the LCS. See if using that will help you (I could write an implementation at some later time).
      singulars
      1. PO
      1. USyumaikas
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload