Longest Common Prefix (LCP) Array

The LCP array records how many initial characters neighboring suffixes share in suffix-array order. It compresses a large amount of repeated-string information into a linear-size array. With SA already built, Kasai’s algorithm computes LCP in O(n) time by reusing knowledge from one text position at the next. LCP reveals the longest repeated substring, enables arbitrary suffix-prefix comparisons with range minima, and counts distinct substrings. The complete program constructs a suffix array using comparison-sort doubling, then builds LCP and counts distinct nonempty substrings. Its total construction cost is therefore O(n log² n); only the additional Kasai stage is linear.

Prerequisites: Suffix arrays, amortized analysis, prefix vs subsequence, range-minimum queries for advanced applications.

Build the idea

1. 1. Fix the array convention first

   We use LCP[0]=0 and LCP[r]=lcp(suffix(SA[r-1]),suffix(SA[r])) for r>0. Other references store the comparison with the next suffix instead; either convention works, but formulas and indices must agree. For banana, SA=[5,3,1,0,4,2] and LCP=[0,1,3,0,0,2]. The pair ana and anana shares ana, length 3; na and nana shares na, length 2. These are contiguous prefixes, not common subsequences.

2. 2. Invert the suffix array

   Kasai visits suffix starts i in original text order, not sorted order. Build inverse[SA[r]]=r so a text position can find its sorted rank immediately. If rank r is positive, the preceding suffix begins at j=SA[r-1]. Compare s[i+h] with s[j+h], where h is a reusable lower bound. Extend h while both indices remain in the text and characters match, then store h into LCP[r]. The rank-zero suffix has no predecessor, so its LCP is zero.

3. 3. Why a previous match can be reused

   Suppose suffix i and its predecessor j share h characters. Removing their first character leaves suffixes i+1 and j+1 sharing at least h-1 characters when h>0. Their lexicographic relative order is preserved after removing that common first character. Although j+1 need not be the immediate predecessor of i+1, every suffix between them in sorted order shares that length-(h-1) prefix. Therefore the immediate predecessor of i+1 also shares it. This proves that the next comparison may start from max(h-1,0), rather than zero.

4. 4. Trace the reused lower bound

   For banana, processing i=1 compares anana with predecessor ana and finds h=3. Before processing i=2, decrement to h=2. Suffix nana has predecessor na, and those two already share na, so the boundary test stops without repeating those character comparisons. Later i=3 compares ana with a, giving h=1. At the suffix with rank zero, reset h to zero. Thinking of h as a guaranteed matching prefix, rather than an answer copied blindly, explains why new matching characters must still be checked.

5. 5. The linear-time argument

   The outer loop visits n positions. Successful character comparisons increase h, while moving to the next position reduces h by at most one, except a reset at the unique rank-zero suffix. The number of increases is bounded by the decreases plus at most the final potential h and the single reset, all O(n). Each iteration also performs only constant failed or boundary checks outside those increases. Thus Kasai performs O(n) work overall even though one pair of suffixes may share almost the whole text.

6. 6. Count distinct substrings

   A suffix beginning at SA[r] contributes n-SA[r] possible nonempty prefixes. Prefixes of length at most LCP[r] have already appeared in an earlier suffix and should not be counted again. Any previously seen prefix of this suffix also occurs in its immediate predecessor, because all suffixes starting with that prefix form a contiguous sorted block. Its new contribution is n-SA[r]-LCP[r]. For banana, summing the contributions gives 15. Equivalently use n(n+1)/2 minus the sum of LCP values. Use long long because this count can be quadratic in n.

7. 7. Beyond neighboring suffixes

   For suffix ranks a<b, their common-prefix length equals min(LCP[a+1..b]). If every neighboring pair in that block agrees on a prefix, every suffix in the block does; if one pair disagrees, the endpoints cannot share more. A sparse table over LCP supports static constant-time range-minimum queries after preprocessing. Equal suffix starts are a special case with answer n-i. The maximum LCP value gives the longest repeated-substring length; repeated occurrences may overlap. None of these applications requires copying all suffix strings.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<numeric>
#include<utility>
using namespace std;
vector<int>suffixArray(const string&s){
    int n=(int)s.size();
    vector<int>sa(n),rank(n),nextRank(n);
    iota(sa.begin(),sa.end(),0);
    // Initial ranks encode one-byte prefixes, not signed char values.
    for(int i=0;i<n;i++){
        rank[i]=(unsigned char)s[i];
    }
    for(int width=1;width<n;width*=2){
        // Missing second halves sort before every real suffix rank.
        auto key=[&](int i){
            return make_pair(rank[i],i+width<n?rank[i+width]:-1);
        };
        sort(sa.begin(),sa.end(),[&](int a,int b){
            return key(a)<key(b);
        });
        // Equal pairs must receive the same new class.
        nextRank[sa[0]]=0;
        for(int j=1;j<n;j++){
            nextRank[sa[j]]=nextRank[sa[j-1]]+(key(sa[j-1])!=key(sa[j]));
        }
        rank.swap(nextRank);
        if(rank[sa.back()]==n-1){
            break; // Every suffix is distinguished.
        }
    }
    return sa;
}
vector<int>buildLCP(const string&s,const vector<int>&sa){
    int n=(int)s.size();
    vector<int>inverse(n),lcp(n,0);
    for(int r=0;r<n;r++){
        inverse[sa[r]]=r;
    }
    int h=0;
    for(int i=0;i<n;i++){
        int r=inverse[i];
        if(r==0){
            h=0;
            continue;
        } // This suffix has no sorted predecessor.
        int j=sa[r-1];
        while(i+h<n&&j+h<n&&s[i+h]==s[j+h]){
            h++;
        }
        lcp[r]=h;
        if(h>0){
            h--; // Removing the first character loses at most one match.
        }
    }
    return lcp;
}
void print(const vector<int>&a){
    for(int i=0;i<(int)a.size();i++){
        if(i){
            cout<<' ';
        }
        cout<<a[i];
    }
    cout<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    getline(cin,s);
    auto sa=suffixArray(s);
    auto lcp=buildLCP(s,sa);
    print(sa);
    print(lcp);
    long long distinct=1LL*s.size()*(s.size()+1)/2;
    for(int x:lcp){
        distinct-=x;
    }
    cout<<distinct<<'\n';
}

Complexity analysis

Suffix array: O(n log² n) time using the included doubling/comparison-sort construction. Kasai after SA: O(n) time and O(n) extra space. Counting: O(n). Total program time O(n log² n), total auxiliary storage O(n). An optional sparse table for LCP range minima would add O(n log n) preprocessing space/time.

Example input and output

One text line, possibly empty or containing spaces, 0≤n≤200000. Output SA on line 1, LCP on line 2 with LCP[0]=0, and the number of distinct nonempty substrings on line 3. For empty text the first two lines are blank and the final line is 0.

Input

banana

Output

5 3 1 0 4 2
0 1 3 0 0 2
15

Neighboring shared-prefix lengths sum to 6. The text has 6×7/2=21 substring occurrences, so there are 21−6=15 distinct nonempty substrings.

Practical applications

Longest repeated substring; number of distinct substrings; longest common prefix of arbitrary suffixes; suffix-array pattern analyses and generalized-string tasks with carefully chosen separators.

Check your understanding

For ranks a<b, which LCP range gives the common-prefix length of those suffixes?

Put it into practice

Print the longest repeated substring, choosing any valid occurrence when there are ties.