module Main where

import Data.Array (Array, (!), array, assocs)
import Data.Ord (comparing)
import Data.List (maximumBy)

lcs :: forall a. Eq a => [a] -> [a] -> [a]
lcs s1 s2 = getSubStr $ maximumBy (comparing snd) $ assocs $ arr
  where
    enum :: [a] -> [(Int, a)]
    enum = zip [1..]
    arr :: Array (Int, Int) Int
    arr = array ((1, 1), (length s1, length s2))
            [((i, j), f x y) | x@(i, _) <- enum s1, y@(j, _) <- enum s2]
    f :: (Int, a) -> (Int, a) -> Int
    f (i, c1) (j, c2)
      | c1 /= c2 = 0
      | i == 1 || j == 1 = 1
      | otherwise = 1 + arr ! (i-1,j-1)
    getSubStr :: ((Int, Int), Int) -> [a]
    getSubStr ((i, _), len) = take len (drop (i-len) s1)

main :: IO () 
main = putStrLn $ lcs "ababc" "babca"