LCP::Manzini - Longest common prefix computation

SYNOPSIS

use LCP::Manzini;

my $Manzini = LCP::Manzini->new();


# -----         Compute lcp array          ----- #
my $LCPArrayRef =$Manzini->lcp(suftab => \@suftab, string => \@strarr);

DESCRIPTION

The longest common prefix (LCP) array is an auxiliary data structure to a suffix array. The array containes lengths of the longest common prefixes (LCPs) between all pairs of consecutive suffixes in a lexicographically ordered array of string suffixes. The algorithm presented here is an implementation of Manzini's linear time space efficient LCP construction solution [1].

new

my $Manzini = LCP::Manzini->new();

Creates a new longest common prefix object.

lcp

my $LCPArrayRef =$Manzini->lcp(suftab => \@suftab, string => \@strarr);

Function requires lexicographically ordered suffix array (suftab) and a string array (string), both as array references. As a result it returns a computed LCP array reference.

AUTHOR

Robert Bakaric <rbakaric@irb.hr>

COPYRIGHT AND LICENSE

Copyright 2015 Robert Bakaric <rbakaric@irb.hr>

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

ACKNOWLEDGEMENT

1. Manzini, G. and Ferragina, P. Engineering a Lightweight Suffix Array Construction Algorithm. 2002.