common-substring.hs

-- from hackerrank.com
-- https://www.hackerrank.com/challenges/common-child

-- define child to be a (not necessarily continuous) substring
-- find the longest sub-child of two strings

import Control.Monad
import Debug.Trace

-- haskell will not do memoization for you
solve :: (Ord a) => [a] -> [a] -> Int
solve [] _ = 0
solve _ [] = 0
solve (x:xs) (y:ys) = 
  if x == y 
    then solve xs ys + 1
    else solve xs (y:ys) `max` solve (x:xs) ys

{-
-- sequential version
iterHelper :: (Ord a) => [a] -> a -> [Int] -> Int -> [Int]
-- assert : length xs == length ls
iterHelper [] _ _ _ = []
iterHelper (x:xs) y (ol:l:ls) ll = d : iterHelper xs y (l:ls) d
  where d = if y == x then ol + 1 else max l ll
iterHelper _ _ (_:_) _ = error "IterList exhausted"
-}

-- turn iterHelper to a tail-call version
iterHelper' :: (Ord a) => [a] -> a -> [Int] -> Int -> [Int] -> [Int]
iterHelper' [] _ _ _ res = reverse res
iterHelper' (x:xs) y (ol:l:ls) ll res = iterHelper' xs y (l:ls) d (d:res)
  where d = if y == x then ol + 1 else max l ll
iterHelper' _ _ (_:_) _ _ = error "IterList exhausted"

ccHelper xs [] ls = head $ reverse ls
ccHelper xs (y:ys) ls = ccHelper xs ys $ iterHelper' xs y (0:ls) 0 []

commonChild :: (Ord a) => [a] -> [a] -> Int
commonChild xs ys = ccHelper xs ys $ replicate (length xs) 0

main = replicateM 2 getLine >>= (\[x, y] -> putStrLn . show $ commonChild x y)
-- main = print $ iterHelper "shabi" 'i' (0:[0,0,0,0,0]) 0