LCPKasai version 1.0
=======================
FULL NAME:
Lowest Common Prefix Computatioin Tool (Kasai et al. [3])
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 package contains the encapsilated sais-light-2.4.1
library written by Yuta Mori [1] implementing the induced sorting [2]
based suffix array construction algorithm and a C++ implementation of
Kasai's linear time LCP construction algorithm [3].
SYNOPSIS:
#include<vector>
#include<string>
#include<SuffixArray.hpp>
#include<LCPArrayKasai.hpp>
string text("This is my text");
/* Make SuffixArray */
/* Construction */
SuffixArray<int|long|unsigned|double> SA(text);
/* OR */
SuffixArray<int|long|unsigned|double> SA;
SA.make(text);
/* Get Suffix Array */
vector<int|long|unsigned|double>SArray = SA.GetSuffixArray(); // [15 4 7 10 0 12 1 2 5 8 3 6 14 11 13 9]
/* Compute LCP array */
LCPArrayKasai<int|long|unsigned|double> LCP(SArray);
/* Get LCP Array */
vector<int|long|unsigned|double>LCPArray = LCP.GetLCPArray(); //[]
CONSTRUCTION AND RUNTIME COMPLEXITY:
For:
|S| - input string size
The algorithm runs in O(|S|) worst-case time
ACKNOWLEDGMENTS:
1. Yuta Mori, 2010. https://sites.google.com/site/yuta256/sais
2. Ge Nong, Sen Zhang and Wai Hong Chan, Two Efficient Algorithms
for Linear Suffix Array Construction, 2008.
3. Kasai, Toru and Lee, Gunho and Arimura, Hiroki and Arikawa, Setsuo and Park, Kunsoo,
Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications,
Lecture Notes in Computer Science, Combinatorial Pattern Matching, 2001.
AUTHOR:
Robert Bakaric <rbakaric@irb.hr>, <bakaric@evolbio.mpg.de>
COPYRIGHT AND LICENSE:
* Copyright 2015 Robert Bakaric
*
* 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.