主页 > 知识库 > Ruby实现的最长公共子序列算法

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

热门标签:白银外呼paas系统 百度地图标注自定义图片 常德电销平台外呼系统软件价格 湖州u友防封电销卡 电销机器人厂商代理 徐州网络外呼系统哪个好 地图标注赚钱项目注册 高德地图标注客服 滴滴外呼系统

最长公共子序列,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 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 %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
   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)

您可能感兴趣的文章:
  • C语言求两个字符串的最长公共子串
  • C++实现寻找最低公共父节点的方法
  • JavaScript自定义函数实现查找两个字符串最长公共子串的方法
  • 深入解析最长公共子串
  • Python最长公共子串算法实例
  • java实现求两个字符串最长公共子串的方法
  • java实现字符串匹配求两个字符串的最大公共子串
  • 利用C++实现最长公共子序列与最长公共子串

标签:公主岭 辽宁 荆门 三沙 张家界 普洱 永州 梧州

巨人网络通讯声明:本文标题《Ruby实现的最长公共子序列算法》,本文关键词  Ruby,实现,的,最长,公共,;如发现本文内容存在版权问题,烦请提供相关信息告之我们,我们将及时沟通与处理。本站内容系统采集于网络,涉及言论、版权与本站无关。
  • 相关文章
  • 下面列出与本文章《Ruby实现的最长公共子序列算法》相关的同类信息!
  • 本页收集关于Ruby实现的最长公共子序列算法的相关信息资讯供网民参考!
  • 企业400电话

    智能AI客服机器人
    15000

    在线订购

    合计11份范本:公司章程+合伙协议+出资协议+合作协议+股权转让协议+增资扩股协议+股权激励+股东会决议+董事会决议

    推荐文章