Ruby实现的最长公共子序列算法

#encoding: utf-8
#author: xu jin,4100213
#date: Nov 01,2012
#Longest-Commom-Subsequence
#to find a longest commom subsequence of two given character arrays by using LCS algorithm
#example output:
#The random character arrays are: ["b","a","c","b","d"] and ["a","b"]
#The Longest-Commom-Subsequence is: a c a a b

chars = ("a".."e").to_a
x,y = [],[]
1.upto(rand(5) + 5) { |i| x << chars[rand(chars.size-1)] }
1.upto(rand(5) + 5) { |i| y << chars[rand(chars.size-1)] }
printf("The random character arrays are: %s and %sn",x,y)
c = Array.new(x.size + 1){Array.new(y.size + 1)}
b = Array.new(x.size + 1){Array.new(y.size + 1)}

def LCS_length(x,y,c,b) 
   m,n = x.size,y.size
   (0..m).each{|i| c[i][0] = 0}
   (0..n).each{|j| c[0][j] = 0}
   for i in (1..m) do
    for j in(1..n) do
    if(x[i - 1] == y [j - 1])
     c[i][j] = c[i - 1][j - 1] + 1;
     b[i][j] = 0
    else
     if(c[i - 1][j] >= c[i][j - 1])
      c[i][j] = c[i - 1][j]
      b[i][j] = 1
     else
      c[i][j] = c[i][j - 1]
      b[i][j] = 2
     end
    end
   end
   end
end

def Print_LCS(x,b,i,j)
  return if(i == 0 || j == 0)
  if(b[i][j] == 0)
    Print_LCS(x,i-1,j-1)
    printf("%c ",x[i - 1])
  elsif(b[i][j] == 1)
    Print_LCS(x,j)
  else
    Print_LCS(x,j-1)
  end
end

LCS_length(x,b) 
print "The Longest-Commom-Subsequence is: "
Print_LCS(x,x.size,y.size)