lcs-0.2: lcs.cabal

Name:               lcs
Version:            0.2
License:            OtherLicense
License-File:       COPYING
Extra-source-files: "BSD3", "GPL-2"
Copyright:          Ian Lynagh, 2005
Author:             Ian Lynagh
Maintainer:         igloo@earth.li
Stability:          provisional
Homepage:           http://urchin.earth.li/~ian/cabal/lcs/
Synopsis:           Find longest common sublist of two lists
Description:
    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.
Category:           List
Tested-With:        GHC==6.8.2
Build-Depends:      base, array
Exposed-modules:
    Data.List.LCS, Data.List.LCS.Simple, Data.List.LCS.HuntSzymanski