Ruby实现的最长公共子序列算法
最长公共子序列，LCS，动态规划实现。
#encoding:utf-8
#author:xujin,4100213
#date:Nov01,2012
#Longest-Commom-Subsequence
#tofindalongestcommomsubsequenceoftwogivencharacterarraysbyusingLCSalgorithm
#exampleoutput:
#Therandomcharacterarraysare:["b","a","c","a","a","b","d"]and["a","c","a","c","a","a","b"]
#TheLongest-Commom-Subsequenceis:acaab
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("Therandomcharacterarraysare:%sand%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)}
defLCS_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}
foriin(1..m)do
forjin(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
defPrint_LCS(x,b,i,j)
returnif(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"TheLongest-Commom-Subsequenceis:"
Print_LCS(x,b,x.size,y.size)
热门推荐
1 如何训练狗狗不叫
2 训练狗狗不叫
3 训练狗狗随行
4 怎么训练狗狗不叫
7 训练比熊狗狗教程
10 上海狗狗训练
11 怎么训练狗狗上厕所
12 训练狗狗趴下
13 狗狗服从训练
14 训练狗狗拒食
15 训练狗狗笑
16 训练狗狗大便
17 训练狗狗立
18 训练狗狗捡东西