The lcs package

[Tags: library]

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(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 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(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.


Properties

Version0.2
Dependenciesarray, base
LicenseOtherLicense
CopyrightIan Lynagh, 2005
AuthorIan Lynagh
Maintainerigloo@earth.li
Stabilityprovisional
CategoryList
Home pagehttp://urchin.earth.li/~ian/cabal/lcs/
Upload dateFri Feb 1 17:01:45 UTC 2008
Uploaded byIanLynagh
Downloads277 total (46 in last 30 days)

Modules

[Index]

Downloads

Maintainers' corner

For package maintainers and hackage trustees