LCPArray.java

packagecom.jwetherell.algorithms.data_structures;

importjava.util.ArrayList;

/**
 * In computer science, the longest common prefix array (LCP array) is an auxiliary
 * data structure to the suffix array. It stores the lengths of the longest common
 * prefixes (LCPs) between all pairs of consecutive suffixes in a sorted suffix array.
 * <p>
 * @see <a href="https://en.wikipedia.org/wiki/LCP_array">LCP Array (Wikipedia)</a>
 * <br>
 * @author Jakub Szarawarski <kubaszarawarski@gmail.com>
 * @author Justin Wetherell <phishman3579@gmail.com>
 */
publicclassLCPArray<CextendsCharSequence> {

privatestaticfinalcharDEFAULT_END_SEQ_CHAR = '$';

privatefinalcharendSeqChar;

privateSuffixArraysuffixArray;
privateArrayList<Integer> lcp;

publicLCPArray(Csequence){
this(sequence, DEFAULT_END_SEQ_CHAR);
 }

publicLCPArray(Csequence, charendChar) {
endSeqChar = endChar;
suffixArray = newSuffixArray(sequence, endSeqChar);
 }

publicArrayList<Integer> getLCPArray() {
if (lcp == null)
LCPAlgorithm();
returnlcp;
 }

privatevoidLCPAlgorithm() {
finalArrayList<Integer> LCPR = getLCPR();
getLCPfromLCPR(LCPR);
 }

privateArrayList<Integer> getLCPR() {
finalArrayList<Integer> KMRArrayList = suffixArray.getKMRarray();
finalArrayList<Integer> suffixArrayList = suffixArray.getSuffixArray();
finalStringstring = suffixArray.getString();
finalintlength = KMRArrayList.size();
finalArrayList<Integer> LCPR = newArrayList<Integer>(); // helper array, LCP[i] = LCPR[suffixArray[i]]

intstartingValue = 0;
for (inti=0; i<length; i++) {
if(KMRArrayList.get(i).equals(0)) {
LCPR.add(0);
startingValue = 0;
 } else {
intLCPRValue = startingValue;
finalintpredecessor = suffixArrayList.get(KMRArrayList.get(i)-1);
while (string.charAt(i+LCPRValue) == string.charAt(predecessor+LCPRValue))
LCPRValue++;
LCPR.add(LCPRValue);
startingValue = LCPRValue-1 > 0 ? LCPRValue-1 : 0;
 }
 }

returnLCPR;
 }

privatevoidgetLCPfromLCPR(ArrayList<Integer> LCPR) {
finalArrayList<Integer> suffixArrayList = suffixArray.getSuffixArray();
finalintlength = suffixArrayList.size();

lcp = newArrayList<Integer>();
lcp.add(null); //no value for LCP[0]
for (inti=1; i<length; i++)
lcp.add(LCPR.get(suffixArrayList.get(i)));
 }
}