lcs: Find longest common sublist of two lists

[ library, list ] [ Propose Tags ]

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.


Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


  • No Candidates
Versions [RSS] 0.2
Dependencies array, base [details]
License LicenseRef-OtherLicense
Copyright Ian Lynagh, 2005
Author Ian Lynagh
Category List
Home page
Uploaded by IanLynagh at 2008-02-01T17:01:45Z
Reverse Dependencies 3 direct, 2 indirect [details]
Downloads 2239 total (9 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]