Longest Common Subsequence

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)*\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*\log \left(m+n\right)\right)$ time in the worst case.