lcs: Find longest common sublist of two lists
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.
Downloads
- lcs-0.2.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
Maintainer's Corner
For package maintainers and hackage trustees
Candidates
- No Candidates
Versions [RSS] | 0.2 |
---|---|
Dependencies | array, base [details] |
Tested with | ghc ==6.8.2 |
License | LicenseRef-OtherLicense |
Copyright | Ian Lynagh, 2005 |
Author | Ian Lynagh |
Maintainer | igloo@earth.li |
Category | List |
Home page | http://urchin.earth.li/~ian/cabal/lcs/ |
Uploaded | by IanLynagh at 2008-02-01T17:01:45Z |
Distributions | |
Reverse Dependencies | 3 direct, 2 indirect [details] |
Downloads | 2309 total (4 in the last 30 days) |
Rating | (no votes yet) [estimated by Bayesian average] |
Your Rating | |
Status | Docs uploaded by user Build status unknown [no reports yet] |