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", "a", "a", "b", "d"] and ["a", "c", "a", "c", "a", "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 = 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, b, i-1, j-1)
    printf("%c ", x[i - 1])
  elsif(b[i][j] == 1)
    Print_LCS(x, b, i-1, j)
  else
    Print_LCS(x, b, i, j-1)
  end
end

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

看完后你知道Ruby怎么实现最长公共子序列算法了吗？相信会对大家有一定的帮助的，切不可生搬硬套，如果你对本文还有问题，也可以联系我们。