Sha256: 8906dc494edeb5e7f03bcdfa1fc336206c88a64112494d199b90977988ff6b0f
Contents?: true
Size: 654 Bytes
Versions: 5
Compression:
Stored size: 654 Bytes
Contents
class String
def lcs(s2)
s1=self
res=""
num=Array.new(s1.size){Array.new(s2.size)}
len,ans=0
lastsub=0
s1.scan(/./).each_with_index do |l1,i |
s2.scan(/./).each_with_index do |l2,j |
unless l1==l2
num[i][j]=0
else
(i==0 || j==0)? num[i][j]=1 : num[i][j]=1 + num[i-1][j-1]
if num[i][j] > len
len = ans = num[i][j]
thissub = i
thissub -= num[i-1][j-1] unless num[i-1][j-1].nil?
if lastsub==thissub
res+=s1[i,1]
else
lastsub=thissub
res=s1[lastsub, (i+1)-lastsub]
end
end
end
end
end
res
end
end
Version data entries
5 entries across 5 versions & 1 rubygems