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

NAME

LCP::Kasai - Longest common prefix computation

SYNOPSIS

use LCP::Kasai;

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


# -----         Compute lcp array          ----- #
my $LCPArrayRef =$Kasai->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 Kasai's linear time LCP construction solution [1].

new

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

Creates a new longest common prefix object.

lcp

my $LCPArrayRef =$Kasai->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. Kasai et al. Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications. 2001.