fork download
copy 
  1. /*
  2.  *
  3.  * Description: Longest Common Subsequence
  4.  *
  5.  * Author     : Adrian Statescu <http://t...content-available-to-author-only...p.ch>
  6.  * 
  7.  * License    : MIT
  8.  *
  9.  */
  10. package main
  11.  
  12. import "fmt"
  13.  
  14. func max(a,b int) (int) {
  15.  
  16.      if a > b {
  17.  
  18.      	return a
  19.  
  20.      } else { 
  21.  
  22.      	return b
  23.      }	
  24. }
  25.  
  26. func createSubseq(lcs [][]int, x []int, y []int, i int, j int) {
  27.  
  28.      if i == 0 || j == 0 {
  29.      	return
  30.      }
  31.  
  32.      if x[i] == y[j] {
  33.  
  34.      	createSubseq(lcs, x, y, i-1, j-1)
  35.  
  36.      	fmt.Printf("%d ", x[i])
  37.  
  38.      } else {
  39.  
  40.         if(lcs[i][j-1] < lcs[i-1][j]) {
  41.  
  42.         	createSubseq(lcs, x, y, i - 1, j)
  43.  
  44.         } else {
  45.  
  46.         	createSubseq(lcs, x, y, i, j - 1)
  47.  
  48.         }
  49.      }
  50. }
  51.  
  52. func main() {
  53.  
  54.      x := []int{0,1,7,3,5,8}
  55.  
  56.      y := []int{0,7,5,8,1}
  57.  
  58.      var n, m int;
  59.  
  60.      n = len(x)
  61.  
  62.      m = len(y)
  63.  
  64.      lcs := make([][]int, n)
  65.  
  66.          for i:= range lcs {
  67.  
  68.          	  lcs[i] = make([]int, m)
  69.          }
  70.  
  71.      for i := 1; i <= n - 1; i++ {
  72.  
  73.      	  for j := 1; j <= m - 1; j++ {
  74.  
  75.              if x[i] == y[j]  {
  76.  
  77.                 lcs[ i ][ j ] = 1 + lcs[i - 1][j - 1]
  78.  
  79.              } else {
  80.  
  81.              	lcs[ i ][ j ] = max(lcs[i][j - 1], lcs[ i -1 ][ j ])
  82.  
  83.              }
  84.  
  85.      	 } 	
  86.  
  87.      }
  88.  
  89.      fmt.Printf("%d\n", lcs[n-1][m-1]) 
  90.  
  91.      createSubseq(lcs, x, y, n - 1, m - 1) 
  92.  
  93.      i := n - 1
  94.      j := m - 1
  95.  
  96.      var ans []int
  97.  
  98.      for i != 0 && j != 0 {
  99.  
  100.          if x[i] == y[j] {
  101.  
  102.             ans = append(ans, x[i]) //push
  103.  
  104.             i = i - 1
  105.             j = j - 1    
  106.  
  107.          }  else {
  108.  
  109.          	if lcs[i][j-1] < lcs[i-1][j] {
  110.  
  111.          		i = i - 1; 
  112.  
  113.          	} else {
  114.  
  115.          		j = j - 1;
  116.          	}
  117.  
  118.          }
  119.      }
  120.  
  121.      fmt.Println("")
  122.  
  123.      for len(ans) > 0 {
  124.  
  125.      	 n := len(ans) - 1
  126.  
  127.      	 fmt.Printf("%d ", ans[n]) //top element
  128.  
  129.      	 ans = ans[:n] //pop
  130.      }
  131.  
  132.      fmt.Println("")
  133. }
Success #stdin #stdout 0s 4344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
7 5 8 
7 5 8
https://ideone.com/ZlRcR7
Longest Common Subsequence in Golang.
language:
Go (go 1.12.1)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!