-
Notifications
You must be signed in to change notification settings - Fork 1
/
lcs.cabal
35 lines (34 loc) · 1.37 KB
/
lcs.cabal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
Name: lcs
Version: 0.2.1
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