NAME

LCP - Longest common prefix computation 


SYNOPSIS 0

    use LCP::Kasai;
    use LCP::Karkkainen;

    my $Kasai = LCP::Kasai->new();
    my $Karkkainen = LCP::Karkkainen->new();
    my $Manzini = LCP::Manzini->new();
   
    my @strarr = qw(t h i s i s a t e s t t o t e s t t h e c o r r e c t n e s s o f L C P K a s a i a l g o r i t h m $);
    my @suftab = qw(50 34 36 33 35 39 41 37 6 20 25 19 24 28 14 8 32 43 18 1 48 40 4 2 46 42 49 27 31 44 21 12 23 45 22 38 5 3 30 29 15 9 13 7 17 0 47 26 11 16 10);

    
    # -----         Compute lcp array          ----- #
    my $lcpKasai =$Kasai->lcp(suftab => \@suftab, string => \@strarr);
    my $lcpKarkk =$Karkkainen->lcp(suftab => \@suftab, string => \@strarr);
    my $lcpManz  =$Manzini->lcp(suftab => \@suftab, string => \@strarr);





DESCRIPTION

The longest common prefix (LCP) array is an auxiliary data struc-
ture 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 algorithms presented here are 
implementations of: Kasai’s linear time LCP construction strategy [1], 
Karkkainen's PLCP based LCP construction strategy [2], Manzini's
space efficient LCP construction strategy [3]


SYNOPSIS 1

        use LCP::Kasai;
    
        my $Kasai = LCP::Kasai->new();
    
    
        # -----         Compute lcp array          ----- #
        my $LCPArrayRef =$Kasai->lcp(suftab => \@suftab, string => \@strarr);


 new

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

    Function creates a new longest common prefix object.

 lcp

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

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

SYNOPSIS 2

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

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

    Creates a new longest common prefix object.

 lcp

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

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


SYNOPSIS 3

        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);


 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>

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.
    

ACKNOWLEDGEMENTS

1.  Kasai et al. Linear-Time Longest-Common-Prefix Computation in 
    Suffix Arrays and Its Applications. 2001.
    
2.  Karkkainen et al. Permuted Longest-Common-Prefix Array. 2009.

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