LCS -- naiver Algorithmus (exponentiell)

-- | Länge einer längsten gemeinsamen Teilfolge
lcs :: Eq a => [a] -> [a] -> Int
lcs [] ys = 0 
lcs xs [] = 0
lcs (x : xs) (y : ys) = 
  maximum 
    [ if x == y then 1 + lcs xs ys
                else     lcs xs ys
    , lcs      xs  (y : ys)
    , lcs (x : xs)      ys 
    ]