# The lcs package

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

Versions | 0.2 |
---|---|

Dependencies | array, base [details] |

License | OtherLicense |

Copyright | Ian Lynagh, 2005 |

Author | Ian Lynagh |

Maintainer | igloo@earth.li |

Stability | provisional |

Category | List |

Home page | http://urchin.earth.li/~ian/cabal/lcs/ |

Uploaded | Fri Feb 1 17:01:45 UTC 2008 by IanLynagh |

Distributions | NixOS:0.2 |

Downloads | 684 total (11 in the last 30 days) |

Votes | |

Status | Docs uploaded by user Build status unknown [no reports yet] |

## Downloads

- lcs-0.2.tar.gz [browse] (Cabal source package)
- Package description (included in the package)