Lcs.hs

module Lcs where
import Data.Array


makeTable xs ys = tbl
    where
      n = length xs
      m = length ys
      tbl :: Array (Int,Int) Integer
      tbl = array ((0,0),(n,m))  [let x = if (xs!!(i-1)) == (ys!!(j-1)) then 1 else 0 
                                  in ((i,j), if i==0 || j==0 then 0 else
                                                 maximum [ tbl!(i-1, j-1) + x
                                                         , tbl!(i-1, j)
                                                         , tbl!(i,   j-1)
                                                         ] )
                                      | (i,j) <- range((0,0),(n,m)) ]


printLcs lcs xs ys = reverse . printLcs' n $ m
    where
      n = length xs
      m = length ys
      printLcs' 0 _ = ""
      printLcs' _ 0 = ""
      printLcs' i j 
                | xs!!(i-1) == ys!!(j-1) = (xs!!(i-1)) : next
                | otherwise            = if lcs!(i-1,j) >= lcs!(i,j-1) then printLcs' (i-1) j else printLcs' i (j-1)
                where next = printLcs' (i-1) (j-1)

lcs xs ys = printLcs (makeTable xs $ ys) xs ys