Latest release:
lcs 0.1.

Haddock docs.

This cabal package provides a function lcs that takes two
lists and returns a longest common sublist. For example,
`lcs "abcd" "acbd"`

is either `"abd"`

or `"acd"`

.

The package provides a simple, stupid and (most of all) slow implementation that needs, for inputs of length $m$ and $n$, $O\left(m+n\right)$ space and $O\left(\left(m+n\right)!\right)$ time in the worst case.

It also provides an implementation of the Hunt-Szymanski LCS
algorithm, based on that in
"String searching algorithms" 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\left(r+m+n\right)$
space and
$O\left(\left(r+m+n\right)*\mathrm{log}\left(m+n\right)\right)$
time. Thus this is
$O\left({\left(m+n\right)}^{2}\right)$
space and
$O\left({\left(m+n\right)}^{2}*\mathrm{log}\left(m+n\right)\right)$
time in the worst case.