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)