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

技术  /  管理员 发布于 5年前   455

最长公共子序列，LCS，动态规划实现。

#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 bchars = ("a".."e").to_ax, 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 %s\n", 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   endenddef 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)  endendLCS_length(x, y, c ,b) print "The Longest-Commom-Subsequence is: "Print_LCS(x, b, x.size, y.size)