Longest Common Subsequence implemented with Bit-Vectors
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
lib/LCS little improvement Jan 18, 2016
t removed debug test Jan 13, 2016
xt
.gitignore
.travis.yml initial port from Perl5 Jan 10, 2016
META6.json
README.md works now for length > 64; improved doc Jan 13, 2016

README.md

NAME

LCS::BV - Bit Vector (BV) implementation of the Longest Common Subsequence (LCS) Algorithm

html

P6-LCS-BV

SYNOPSIS

  use LCS::BV;

  $lcs = LCS::BV::LCS($a,$b);

ABSTRACT

LCS::BV implements the Longest Common Subsequence (LCS) Algorithm and is more than double as fast (Jan 2016) than Algorithm::Diff::LCSidx().

DESCRIPTION

This module is a port from the Perl5 module with the same name.

The algorithm used is based on

H. Hyyroe. A Note on Bit-Parallel Alignment Computation. In
M. Simanek and J. Holub, editors, Stringology, pages 79-87. Department
of Computer Science and Engineering, Faculty of Electrical
Engineering, Czech Technical University, 2004.

METHODS

  • LCS($a,$b)

Finds a Longest Common Subsequence, taking two arrayrefs as method arguments. It returns an array reference of corresponding indices, which are represented by 2-element array refs.

SEE ALSO

Algorithm::Diff

AUTHOR

Helmut Wollmersdorfer lthelmut.wollmersdorfer@gmail.comgt