#Longest Common Subsequence Algorithm Implementation
#Pesudocode(wikipedia)->ruby translation(me)
#by Steve Hanna
#http://www.vividmachines.com/6 on ttyp1
#v.01

def ma(i,j,w)
  w*j+i
end

def print_matrix(matrix, x, y)
(0...x).each { |xx| (0...y).each { |yy| print matrix[ma(xx,yy,x)]," "; print "\n" if yy == y-1}  }
end 

def backtrack(m,s1,s2,i,j,w)
  if i == 0 || j == 0 then
        return ""
  elsif s1[i-1] == s2[j-1] then
        return backtrack(m,s1,s2,i-1,j-1,w) + s1[i-1,1]
  else
        if m[ma(i,j-1,w)] > m[ma(i-1,j,w)] then
                return backtrack(m,s1,s2,i,j-1,w)
        else
                return backtrack(m,s1,s2,i-1,j,w)
        end
  end
end

def find_lcs(s1,s2)
  x,y = s1.length + 1, s2.length + 1
  m = Array.new(x*y)
  (0...x).each { |xx| m[ma(xx,0,x)] = 0} 
  (0...y).each { |yy| m[ma(0,yy,x)] = 0}
  
  (1...x).each { |xx| 
          (1...y).each { |yy|
                if s1[xx-1] == s2[yy-1] then
                  m[ma(xx,yy,x)] = m[ma(xx-1,yy-1,x)] + 1
                else
                  m[ma(xx,yy,x)] = [ m[ma(xx,yy-1,x)], m[ma(xx-1,yy,x)] ].max 
                end
        }
  }
  print "longest common subsequence\n"
  print "string1: #{s1}\nstring2: #{s2}\n"
  print "lcs: ",backtrack(m,s1,s2,x,y,x),"\n\n"
  print_matrix(m,x,y)
end

exit unless ARGV[0] and ARGV[1]
find_lcs(ARGV[0],ARGV[1])