-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Find longest common sublist of two lists
--   
--   Provides a function lcs that takes two lists and returns a longest
--   common sublist. For example, lcs <a>abcd</a> <a>acbd</a> is either
--   <a>abd</a> or <a>acd</a>.
--   
--   The package provides a simple, stupid and (most of all) slow
--   implementation that needs, for inputs of length m and n, O(m+n) space
--   and O((m+n)!) time in the worst case.
--   
--   It also provides an implementation of the Hunt-Szymanski LCS
--   algorithm, based on that in <a>String searching algorithms</a> by
--   Graham A Stephen, ISBN 981021829X.
--   
--   Given inputs xs and ys of length m and n respectively, where there are
--   r pairs (x, y) where x is in xs, y is in ys and x == y, Hunt-Szymanski
--   needs O(r+m+n) space and O((r+m+n)*log(m+n)) time. Thus this is
--   O((m+n)^2) space and O((m+n)^2*log(m+n)) time in the worst case.
@package lcs
@version 0.2


-- | This is a simple, stupid and (most of all) slow implementation of the
--   Data.List.LCS interface.
module Data.List.LCS.Simple
lcs :: Ord a => [a] -> [a] -> [a]


-- | This is an implementation of the Hunt-Szymanski LCS algorithm. Derived
--   from the description in "String searching algorithms" by Graham A
--   Stephen, ISBN 981021829X.
module Data.List.LCS.HuntSzymanski

-- | The <a>lcs</a> function takes two lists and returns a list with a
--   longest common subsequence of the two.
lcs :: Ord a => [a] -> [a] -> [a]


-- | Provides a function lcs that takes two lists and returns a longest
--   common sublist. For example, lcs <a>abcd</a> <a>acbd</a> is either
--   <a>abd</a> or <a>acd</a>.
module Data.List.LCS

-- | The <a>lcs</a> function takes two lists and returns a list with a
--   longest common subsequence of the two.
lcs :: Ord a => [a] -> [a] -> [a]