/ 
LCP-0.01
River stage zero No dependents
/ LCP::Karkkainen

NAME

LCP::Karkkainen - Longest common prefix computation

SYNOPSIS

use LCP::Karkkainen;

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

# -----         Compute lcp array          ----- #
my $lcparray =$Karkkainen->lcp(suftab => \@suftab, string => \@array);
my $plcparray =$Karkkainen->plcp(suftab => \@suftab, string => \@array);

DESCRIPTION

The longest common prefix (LCP) array is an auxiliary data structure to the suffix array. The array containes lengths of the longest common prefixes (LCPs) between all pairs of consecutive suffixes in a sorted suffix array. The algorithm presented here is an implementation of Karkkainen's linear time PLCP and LCP construction strategies [1].

new

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

Creates a new longest common prefix object.

lcp

   my $lcparray =$Karkkainen->lcp(suftab => \@suftab, string => \@array);

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

plcp

my $plcparray =$Karkkainen->plcp(suftab => \@suftab, string => \@array);

Function requires a sorted suffix array (suftab) and a string (string) both as array references. As a result it returns computed PLCP array (an array of permuted LCP values as they appear in the string)

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. Karkkainen et al. Permuted Longest-Common-Prefix Array. 2009.