NAME

Algorithm::LCS - Fast (XS) implementation of the Longest Common Subsequence (LCS) Algorithm

SYNOPSIS

  use Algorithm::LCS;

  $alg = Algorithm::LCS->new;
  @lcs = $alg->LCS(\@a,\@b);

  $cb = $alg->callback(@b); # closure
  @lcs = $cb->(\@a);        # same result as prior LCS() call

ABSTRACT

Algorithm::LCS reimplements Algorithm::Diff's core loop in XS, and provides a simple OO interface to it.

Extract from the Algorithm::Diff v1.15 manpage:

  The algorithm is that described in 
  I<A Fast Algorithm for Computing Longest Common Subsequences>,
  CACM, vol.20, no.5, pp.350-353, May 1977, with a few
  minor improvements to improve the speed.

DESCRIPTION

CONSTRUCTOR

new(): Creates a new object which maintains internal storage areas for the LCS computation. Use one of these per concurrent LCS() call.

METHODS

line_map(@lines)

Send @lines to a hashref containing elements of the form

       value => [(increasing) list of matching indices]

callback(@lines)

Generates a closure capturing the object and line_map hash for @lines. Most useful when computing multiple LCSs against a single file.

LCS(\@a,\@b)

Finds a Longest Common Subsequence, taking two arrayrefs as method arguments. In scalar context the return value is the length of the subsequence. In list context it yields a list of corresponding indices, which are represented by 2-element array refs. See the Algorithm::Diff manpage for more details.