fork download
copy 
  1. def createSub lcs, x, y, i, j
  2.  
  3.      if i == 0 or j == 0  
  4.  
  5.     	return
  6.  
  7.      end	
  8.  
  9.     	if x[ i ].to_i == y[ j ].to_i
  10.  
  11.     	   createSub(lcs, x, y, i - 1, j - 1)
  12.  
  13.     	   print x[i], " " 	   
  14.  
  15.     	else
  16.  
  17.     		if lcs[ i ][ j - 1] < lcs[ i - 1 ][ j ]
  18.  
  19.     			createSub(lcs, x, y, i - 1, j)
  20.  
  21.     		else
  22.  
  23.                 createSub(lcs, x, y, i, j - 1)
  24.  
  25.     	    end	
  26.  
  27.     	end	    
  28. end
  29.  
  30. def max a,b
  31.  
  32.     if a > b
  33.     	return a
  34.     else
  35.     	return b
  36.     end 	
  37. end	
  38.  
  39. def main    
  40.  
  41. 	x = [0, 1, 7, 3, 5, 8]	
  42.     y = [0, 7, 5, 8, 1]
  43.  
  44.     n = x.length() - 1
  45.     m = y.length() - 1
  46.  
  47.     lcs = Array.new(n+1){Array.new(m+1,0)} 
  48.  
  49.     1.upto(n) { 
  50.  
  51.     	|i|
  52.  
  53.     	1.upto(m) {
  54.  
  55.     		|j|
  56.  
  57.             if x[i].to_i == y[j].to_i
  58.  
  59.                 lcs[i][j] = 1 + lcs[i-1][j-1].to_i       
  60.  
  61.     		else
  62.  
  63.     			lcs[i][j] = max(lcs[i][j-1].to_i, lcs[i-1][j].to_i)
  64.     	    end
  65.     	}
  66.  
  67.     } 
  68.  
  69.     p lcs[n][m]
  70.  
  71.     createSub(lcs, x, y, n, m)
  72. end   
  73.  
  74. main
Success #stdin #stdout 0.01s 6236KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
7 5 8
https://ideone.com/SzQ7lP
Longest Common Subsequence in Ruby.
language:
Ruby (ruby 2.5.5)
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!