Longest Common Prefix Array: Algorithm Analysis and Code

1. Introduction and Core Concepts

The Longest Common Prefix (LCP) array is one of the most fundamental auxiliary data structures in string algorithms, intimately tied to the suffix array and suffix tree. While the suffix array itself provides the lexicographically sorted order of all suffixes of a string, it does not directly tell us how much consecutive suffixes in that sorted order have in common. The LCP array fills this gap by storing the length of the longest common prefix between each pair of adjacent suffixes in the suffix array.

Formally, given a string S of length n and its suffix array SA where SA[i] is the starting index of the i-th lexicographically smallest suffix, the LCP array is defined as an array of length n where LCP[0] = 0 (or undefined) and for i > 0, LCP[i] = lcp(S[SA[i]..], S[SA[i-1]..]), i.e., the length of the longest common prefix of the suffixes at SA[i] and SA[i-1]. Some definitions use an array of length n-1 where LCP[i] = lcp(SA[i], SA[i+1]); both conventions are equivalent with a shift in indexing.

Understanding the LCP array is crucial because it transforms the suffix array from a simple ordering into a powerful tool for analyzing the internal structure of a string. Without it, many queries that should be efficient become expensive. For example, finding the longest repeated substring, counting distinct substrings, or finding the longest common substring between two strings can all be reduced to range minimum queries over the LCP array. Its importance lies in its ability to quantify similarity between lexicographically close suffixes, which is the foundation for almost all advanced string processing.

Why the LCP Array Matters

The primary motivation for the LCP array is efficiency. A naive comparison of two suffixes can take O(n) time, and doing this for all adjacent pairs would be prohibitively expensive. The LCP array, when constructed in linear time using algorithms like Kasai's, provides this information for all pairs at once. This precomputation enables O(1) or O(log n) queries for many problems after O(n log n) or O(n) preprocessing.

Beyond theoretical elegance, the LCP array is a practical necessity in systems dealing with large textual data. Modern bioinformatics pipelines, search engines, data compression tools, and plagiarism detectors all rely on suffix arrays augmented with LCP arrays to achieve scalability. It is the bridge between sorting suffixes and understanding their shared structure, making it indispensable for any engineer working with string algorithms.

2. How It Works

The mechanism behind the LCP array is best understood through its relationship with the suffix array and the ranking of suffixes. Consider the string S = "banana". Its suffixes are "banana", "anana", "nana", "ana", "na", "a". When sorted lexicographically, the order is "a" (5), "ana" (3), "anana" (1), "banana" (0), "na" (4), "nana" (2). The suffix array is therefore [5, 3, 1, 0, 4, 2]. The LCP array measures the overlap between neighbors in this sorted list: lcp("a", "ana") = 1 ("a"), lcp("ana", "anana") = 3 ("ana"), lcp("anana", "banana") = 0, and so on, yielding [0, 1, 3, 0, 0, 2].

The key theoretical insight that makes efficient construction possible is that the LCP values are not independent. If we know the LCP between a suffix and its predecessor in the suffix array, we can derive information about the LCP of the next suffix. Specifically, let rank[i] be the position of suffix S[i..] in the suffix array. If lcp(S[i..], S[j..]) = k where j is the predecessor of i in the suffix array, then lcp(S[i+1..], S[j+1..]) >= k-1. This is because removing the first character from two strings that share a prefix of length k leaves strings that share a prefix of length k-1. Furthermore, S[j+1..] may not be the predecessor of S[i+1..], but its rank is close, which bounds the search.

This property is the foundation of Kasai's algorithm, the classic linear-time method for building the LCP array. Instead of comparing each adjacent pair in the suffix array from scratch, Kasai's algorithm iterates over the suffixes in their original order (from 0 to n-1) and maintains a running value k that represents the current LCP length. Because k only decreases by at most 1 per iteration and increases at most n times overall, the total number of character comparisons is linear. This amortized analysis is what guarantees O(n) time complexity despite nested loops.

The Role of the Rank Array

The rank array, also called the inverse suffix array, is essential for the linear construction. It is defined as rank[SA[i]] = i. While the suffix array answers "which suffix is i-th in sorted order?", the rank array answers "what is the sorted position of the suffix starting at i?". Kasai's algorithm uses the rank array to quickly find the predecessor of any suffix S[i..] in sorted order: its predecessor starts at SA[rank[i]-1]. This allows the algorithm to process suffixes sequentially by their starting position rather than in sorted order, which is key to reusing the previous LCP value k.

Conceptually, the LCP array encodes the shape of the suffix trie or suffix tree in a flat array. The values in the LCP array correspond to the depths of lowest common ancestors (LCAs) between adjacent leaves in the suffix tree. A large LCP value indicates that two suffixes diverge deep in the tree (they share a long path), while a small value indicates an early divergence. This connection allows many tree-based operations to be simulated efficiently on the array using Range Minimum Query (RMQ) structures.

3. Implementation

Implementing the LCP array correctly requires first having a correct suffix array. For clarity, we will use Python's built-in sort for suffix array construction (O(n log^2 n)), which is sufficient for educational purposes and moderate input sizes. In production systems handling millions of characters, a linear-time suffix array construction algorithm like SA-IS or Skew would be used. Once the suffix array is available, we can implement both the naive and the optimal Kasai construction.

The naive approach directly compares each adjacent pair in the suffix array character by character. While simple to understand, it has a worst-case time complexity of O(n^2), for example on a string like "aaaaa...a", where each comparison can take O(n) time. It serves as a useful baseline for testing the correctness of the optimized version.

def build_suffix_array_naive(s):
    """Build suffix array using Python sort - O(n log^2 n)."""
    n = len(s)
    # Create list of (suffix, index) and sort
    suffixes = [(s[i:], i) for i in range(n)]
    suffixes.sort()
    return [idx for _, idx in suffixes]

def build_lcp_naive(s, sa):
    """Naive LCP construction - O(n^2) worst case."""
    n = len(s)
    lcp = [0] * n
    # lcp[0] is defined as 0
    for i in range(1, n):
        # Get the two adjacent suffixes in SA order
        prev_suffix = s[sa[i-1]:]
        curr_suffix = s[sa[i]:]
        # Count common prefix length
        count = 0
        # Use < for bounds checking
        while count < len(prev_suffix) and count < len(curr_suffix) and prev_suffix[count] == curr_suffix[count]:
            count += 1
        lcp[i] = count
    return lcp

# Example usage
s = "banana"
sa = build_suffix_array_naive(s)
lcp = build_lcp_naive(s, sa)
print(f"String: {s}")
print(f"SA: {sa}")
print(f"LCP: {lcp}")

The efficient Kasai algorithm achieves O(n) time by leveraging the rank array and the prefix monotonicity property. The implementation below is the standard textbook version. Note the critical optimization: the variable k is not reset to zero for each suffix, but is decremented by one from its previous value. This ensures each character in the string is compared at most twice, leading to linear overall work.

def build_lcp_kasai(s, sa):
    """
    Kasai's algorithm for LCP array construction - O(n) time.
    s: input string
    sa: suffix array of s
    Returns: LCP array where lcp[i] = lcp(sa[i], sa[i-1]) for i > 0
    """
    n = len(s)
    if n == 0:
        return []
    
    # Build rank array: rank[sa[i]] = i
    rank = [0] * n
    for i in range(n):
        rank[sa[i]] = i
    
    lcp = [0] * n
    k = 0  # Current lcp length
    
    for i in range(n):
        # If this suffix is first in SA, no predecessor
        if rank[i] == 0:
            k = 0
            continue
        
        # j is the start index of the predecessor suffix in SA
        j = sa[rank[i] - 1]
        
        # Extend k as far as possible
        # s[i+k] == s[j+k] means we can extend the common prefix
        while i + k < n and j + k < n and s[i + k] == s[j + k]:
            k += 1
        
        lcp[rank[i]] = k
        
        # For next iteration, k is at least k-1
        if k > 0:
            k -= 1
    
    return lcp

# Example: s = "abracadabra"
s2 = "abracadabra"
sa2 = build_suffix_array_naive(s2)
lcp2 = build_lcp_kasai(s2, sa2)
print(f"SA for '{s2}': {sa2}")
print(f"LCP: {lcp2}")

For many applications, we need to answer arbitrary LCP queries, not just between adjacent suffixes. The LCP between any two suffixes SA[i] and SA[j] (where i < j) is the minimum value in the LCP array over the interval (i+1 .. j). This is a classic Range Minimum Query (RMQ) problem. By preprocessing the LCP array for RMQ using a Sparse Table (O(n log n) preprocessing, O(1) query) or a Segment Tree (O(n) preprocessing, O(log n) query), we can answer any LCP query efficiently.

import math

def build_sparse_table(arr):
    """Build Sparse Table for RMQ - O(n log n) preprocessing."""
    n = len(arr)
    LOG = math.floor(math.log2(n)) + 1
    st = [[0]* n for _ in range(LOG)]
    st[0] = arr[:]
    
    j = 1
    while (1 << j) <= n:
        i = 0
        while i + (1 << j) - 1 < n:
            # st[j][i] stores min of range [i, i + 2^j -1]
            if st[j-1][i] < st[j-1][i + (1 << (j-1))]:
                st[j][i] = st[j-1][i]
            else:
                st[j][i] = st[j-1][i + (1 << (j-1))]
            i += 1
        j += 1
    return st

def query_rmq(st, l, r):
    """Query minimum in [l, r] inclusive - O(1)."""
    if l > r:
        l, r = r, l
    length = r - l + 1
    k = math.floor(math.log2(length))
    # Compare two overlapping intervals
    if st[k][l] < st[k][r - (1 << k) + 1]:
        return st[k][l]
    else:
        return st[k][r - (1 << k) + 1]

def lcp_query(sa, rank, lcp_st, i, j):
    """Get LCP of suffixes starting at i and j using RMQ."""
    if i == j:
        return len(sa) - i
    ri, rj = rank[i], rank[j]
    if ri > rj:
        ri, rj = rj, ri
    # LCP is min in lcp[ri+1 .. rj]
    return query_rmq(lcp_st, ri + 1, rj)

A complete, self-contained implementation that handles edge cases like empty strings, single-character strings, and strings with unique characters is important for robustness. The following helper also demonstrates how to compute the number of distinct substrings directly from the LCP array, a common application that validates the correctness of the construction.

def count_distinct_substrings(s):
    """
    Count distinct substrings using SA + LCP.
    Formula: total substrings - sum(LCP)
    total = n*(n+1)//2
    """
    n = len(s)
    if n == 0:
        return 0
    sa = build_suffix_array_naive(s)
    lcp = build_lcp_kasai(s, sa)
    total = n * (n + 1) // 2
    # Sum of LCP values counts duplicate prefixes
    distinct = total - sum(lcp)
    return distinct, sa, lcp

def longest_repeated_substring(s):
    """Find longest repeated substring via max LCP value."""
    n = len(s)
    if n <= 1:
        return ""
    sa = build_suffix_array_naive(s)
    lcp = build_lcp_kasai(s, sa)
    max_len = max(lcp)
    if max_len == 0:
        return ""
    # Find index of max LCP
    idx = lcp.index(max_len)
    start = sa[idx]
    return s[start:start + max_len]

# Test
s3 = "banana"
distinct, sa3, lcp3 = count_distinct_substrings(s3)
print(f"Distinct substrings in '{s3}': {distinct}")  # Expected 15
print(f"Longest repeated: '{longest_repeated_substring(s3)}'")  # Expected 'ana'

4. Step-by-Step Example

Let us walk through the construction of the suffix array and LCP array for the string S = "ababa" (n=5). This string is chosen because it has overlapping repetitions and is small enough to trace manually but complex enough to illustrate all steps. The suffixes are: 0:"ababa", 1:"baba", 2:"aba", 3:"ba", 4:"a".

First, we sort the suffixes lexicographically. Comparing them: "a" (4) is smallest, then "aba" (2) ("a" < "ababa" because "a" is a prefix), then "ababa" (0), then "ba" (3), then "baba" (1). Therefore, the suffix array is SA = [4, 2, 0, 3, 1]. We can verify this by listing the sorted suffixes: S[4]="a", S[2]="aba", S[0]="ababa", S[3]="ba", S[1]="baba". The rank array is the inverse: rank[4]=0, rank[2]=1, rank[0]=2, rank[3]=3, rank[1]=4, so rank = [2, 4, 1, 3, 0].

Now we compute the LCP array using Kasai's algorithm, iterating i from 0 to 4. We maintain k, the current prefix length.

Iteration i=0: suffix "ababa". rank[0]=2, so its predecessor in SA is at SA[1]=2 which is "aba". We compare "ababa" and "aba": they share "aba" (length 3). So k=3, we set LCP[2]=3. Then decrement k to 2 for next iteration.

Iteration i=1: suffix "baba". rank[1]=4, predecessor is SA[3]=3 ("ba"). We start with k=2. Compare "baba" and "ba" starting from offset 2: we check s[1+2]='b' vs s[3+2]='' (out of bounds), so no extension. Actually we check while s[1+2]==s[3+2] - but s[3+2] is beyond string, so loop ends. So LCP[4]=2? Wait careful: we compare from k=2: s[1+2]=s[3] vs s[3+2]=s[5] out of bounds, so we keep k=2? Let's trace correctly: i=1, j=3, k=2 initially. Check i+k=3, j+k=5 - j+k is out of bounds, so while fails. Thus LCP[4]=2. But actual lcp("baba","ba") is 2 ("ba"), so correct. Then k becomes 1.

Iteration i=2: suffix "aba". rank[2]=1, predecessor is SA[0]=4 ("a"). Start with k=1. Compare s[2+1]='b' vs s[4+1] out of bounds, so no extension. LCP[1]=1 (lcp("aba","a")=1). k becomes 0.

Iteration i=3: suffix "ba". rank[3]=3, predecessor is SA[2]=0 ("ababa"). Start k=0. s[3]='b' vs s[0]='a' mismatch, so k stays 0. LCP[3]=0. k stays 0.

Iteration i=4: suffix "a". rank[4]=0, no predecessor, skip. Final LCP array: [0, 1, 3, 0, 2]. We can verify by direct comparison: lcp("a","aba")=1, lcp("aba","ababa")=3, lcp("ababa","ba")=0, lcp("ba","baba")=2. The walkthrough demonstrates how k never resets to zero unnecessarily, saving comparisons.

Visualizing the Result

If we write the sorted suffixes with their LCP values as a bar between them, we get:

0: a (LCP 0)
1: aba (LCP 1) - shares "a" with previous
3: ababa (LCP 3) - shares "aba" with previous
0: ba (LCP 0) - no common prefix
2: baba (LCP 2) - shares "ba" with previous

This visualization shows how the LCP array highlights clusters of similar suffixes. The block [a, aba, ababa] forms a cluster with increasing LCP, indicating a repeated pattern "aba". The block [ba, baba] forms another cluster. Such clustering is exactly what algorithms for finding repeats exploit.

5. Complexity Analysis

The efficiency of the LCP array is one of its most attractive properties. The naive construction, which compares each adjacent pair independently, performs up to O(n) work per pair, leading to O(n^2) worst-case time. This occurs on highly repetitive strings like "aaaa...a" where each comparison traverses almost the entire suffix. For random strings over a large alphabet, the average case is much better (close to O(n log n) due to early mismatches), but the worst-case guarantee is poor and unacceptable for large inputs.

Kasai's algorithm provides a strong guarantee: O(n) time and O(n) additional space, regardless of the input string. The time analysis relies on amortized complexity. The variable k starts at 0, is decremented at most n times (once per iteration), and is incremented at most n times overall because each increment corresponds to a successful character match that advances the pointer in the string, and the pointer never moves backward beyond the decrement. Therefore, the total number of iterations of the inner while loop across the entire execution is O(n). The outer loop is O(n), and building the rank array is O(n), so total time is linear.

Space complexity is also linear. We need to store the string (n), the suffix array (n integers), the rank array (n integers), and the LCP array (n integers). Each integer array requires O(n) space. The algorithm itself uses only O(1) extra variables. When combined with a suffix array construction algorithm, the overall space remains O(n). If a Sparse Table is built for RMQ, an additional O(n log n) space is required, which is often the dominant memory cost for applications needing fast arbitrary LCP queries.

* Best case for naive assumes early mismatches and efficient suffix array. The table highlights why Kasai is preferred: it provides a worst-case linear guarantee that naive cannot match. When evaluating overall system performance, the suffix array construction often dominates the runtime, as the fastest practical SA algorithms are O(n log n) (like prefix-doubling) or O(n) with larger constants (SA-IS). Therefore, optimizing SA construction is often more impactful than further optimizing LCP construction, which is already optimal.

Best, Average, and Worst Case Nuances

For Kasai, best, average, and worst cases are all O(n), making it very predictable. This is ideal for systems requiring latency guarantees. For the naive method, the best case occurs when the string has no repeated prefixes, such as a random string over a large alphabet or a string like "abcdef...", where each LCP comparison fails on the first character. In that scenario, naive is also O(n). However, this best case is fragile and not representative of real-world data like genomic sequences or natural language, which contain many repeats. Thus, complexity analysis must consider the data distribution, and Kasai's worst-case optimality makes it the only safe choice for general-purpose libraries.

6. Variations and Optimizations

Several variations and optimizations of the LCP array exist to suit different needs. The most common variant is the definition of the array's length and indexing. As mentioned, some implementations use length n with LCP[0]=0, while others use length n-1 where LCP[i] corresponds to the pair (SA[i], SA[i+1]). The latter is slightly more memory-efficient and aligns with the concept of intervals between suffixes. Another variant is the Permuted LCP (PLCP) array, where PLCP[i] = LCP[rank[i]], i.e., the LCP values are stored in the original string order rather than suffix array order. PLCP is useful because it is more cache-friendly when accessed sequentially and can be computed directly without explicitly permuting.

Kasai's algorithm itself has been optimized for cache performance and constant factors. The original Kasai algorithm accesses the string and rank array in a pattern that may cause cache misses. The Kasai et al. improvement and later the "Kasai with Kasai's trick" or the algorithm by Manzini show how to reduce cache misses by processing differently. A particularly elegant optimization is the Phi algorithm (also called the Kärkkäinen-Manzini-Puglisi algorithm), which avoids the rank array entirely by using the Phi array where Phi[SA[i]] = SA[i-1]. This reduces one level of indirection and can be faster in practice.

For very large alphabets or integer alphabets, the LCP array can be constructed simultaneously with the suffix array using induced sorting (SA-IS). In SA-IS, the LCP values can be derived during the final induction step with minimal extra cost. Another important optimization is for external memory or distributed settings: when the string does not fit in RAM, the LCP array can be constructed in a streaming or divide-and-conquer manner, often using the concept of differential LCP arrays that store differences between consecutive LCP values, which are more compressible.

Choosing the right variant depends on the application. If memory is tight, PLCP or DLCP with Elias coding can reduce the LCP storage from 4n bytes to close to 2n bytes or less for repetitive texts. If query speed is paramount, building a Sparse Table or a Cartesian tree for RMQ is essential. For teaching and general use, the standard Kasai with rank array remains the most readable and sufficiently efficient choice.

Handling Special Cases

Edge cases such as empty strings, strings with a single character, and strings containing sentinel characters require careful handling. Most implementations append a unique terminator character '$' that is lexicographically smaller than any other character to ensure all suffixes are distinct and the suffix array is well-defined. The LCP values involving the sentinel suffix are always zero. When working with multiple strings (e.g., for longest common substring), a common technique is to concatenate them with distinct separators (e.g., "string1#string2$") and build a single suffix array and LCP array, then filter LCP values that span across different original strings.

7. Real-World Applications

The LCP array is not merely an academic curiosity; it powers critical functionality in diverse domains. In bioinformatics, it is central to genome assembly and read mapping. When sequencing a genome, millions of short reads must be assembled. Suffix arrays with LCP arrays allow efficient detection of overlaps between reads by finding long common prefixes between suffixes. Tools like BWA and Bowtie use related structures (FM-index, which is a compressed suffix array) to align reads to a reference genome in sublinear time per read. Finding the longest repeated substring in a genome can reveal repetitive elements like transposons, and counting distinct substrings helps estimate genome complexity.

In data compression, the LCP array is closely related to the Lempel-Ziv factorization. The LZ77 algorithm, which underlies gzip and many other compressors, works by finding the longest previous occurrence of a prefix of the remaining input. This is essentially an LCP query. While practical compressors use hash tables or suffix trees for speed, the theoretical analysis of compression ratios often uses the LCP array. The Burrows-Wheeler Transform (BWT), used in bzip2, is a permutation of the string derived from the suffix array, and the LCP array helps analyze the clustering of similar contexts that makes BWT compressible.

Search engines and information retrieval systems use suffix arrays and LCP arrays for full-text indexing. An inverted index is efficient for word-based search, but substring search (e.g., searching for "fish" inside "flyfishnwa") requires a suffix-based structure. With SA + LCP, one can find all occurrences of a pattern P in O(|P| log n) time via binary search on the suffix array, and the LCP array accelerates this search by avoiding redundant character comparisons (using the LCP values to skip already-matched prefixes, similar to the Kasai trick). Autocomplete and spell-checking systems also use LCP information to suggest completions that share a prefix with the query.

Plagiarism detection and document similarity systems rely on finding long common substrings between documents. By concatenating two documents with a separator and building the combined SA and LCP array, the longest common substring is simply the maximum LCP value where the two suffixes originate from different documents. This approach scales to large corpora and is used in systems like MOSS for code plagiarism detection. Similarly, in version control systems, finding the longest common subsequence or diff can be aided by LCP structures to identify large unchanged blocks quickly.

Systems-Level Uses

At the systems level, web servers and databases use LCP-like concepts for routing and indexing. IP routing tables use longest prefix match to forward packets, and while the data structure there is a trie (like a Patricia trie), the underlying problem is analogous to finding the longest common prefix between an incoming address and stored prefixes. In databases, suffix arrays with LCP are used to index string columns for LIKE queries with wildcards (e.g., 'abc%'), enabling index-accelerated prefix searches without a full table scan. Even in network security, intrusion detection systems scan payloads for known attack signatures using efficient substring search powered by suffix arrays.

8. Comparison with Alternatives

While the LCP array is powerful, it is not the only structure for string processing. The choice between suffix array + LCP, suffix tree, suffix automaton, and other structures depends on the required operations, memory constraints, and implementation complexity. The suffix tree is the most direct alternative: it explicitly represents all suffixes in a tree where edge labels are substrings and each leaf corresponds to a suffix. The LCP array essentially encodes the suffix tree's structure implicitly. A suffix tree can answer many queries in O(m) time where m is the pattern length, which is theoretically faster than the O(m log n) of suffix array binary search, but suffix trees have a large memory overhead (often 10-20x the string size) and are complex to implement correctly (Ukkonen's algorithm).

The suffix automaton (SAM) and suffix trie are automata that recognize all substrings of a string. SAM is minimal and has O(n) states, making it very memory-efficient for certain problems like counting distinct substrings or finding the longest common substring of two strings. However, SAM does not directly provide lexicographic order or the ability to enumerate suffixes in sorted order, which SA+LCP does. The suffix array + LCP combination is often preferred when lexicographic order matters or when simplicity and cache efficiency are priorities, as arrays are more cache-friendly than pointer-based trees or automata.

For prefix-specific problems, a Trie (or its compressed variant, the Radix Tree / Patricia Trie) is the natural choice. Tries are optimized for prefix search and can find the longest common prefix among a set of strings (not suffixes of a single string) very efficiently. However, a trie of all suffixes is essentially a suffix tree/trie, which brings us back to the previous comparison. For a static set of independent strings (like a dictionary), a trie is better than building a suffix array of their concatenation. The LCP array's niche is specifically for analyzing the suffixes of one (or a few) long strings.

In practice, the suffix array + LCP array has largely replaced suffix trees in many applications due to its smaller memory footprint and better cache performance, despite a slightly slower query time. The constant factors matter: a binary search over an array is often faster than traversing a tree with poor locality, even if the asymptotic complexity is worse. Libraries like libdivsufsort provide highly optimized suffix array construction that is used in production systems, making SA+LCP the pragmatic default choice for most engineers.

9. Common Mistakes and Best Practices

Implementing the LCP array correctly is deceptively tricky, and several common pitfalls can lead to subtle bugs or performance issues. One of the most frequent mistakes is an off-by-one error in indexing. As noted, there are two conventions for LCP length (n vs n-1) and for whether LCP[0] is defined. Mixing these conventions when integrating code from different sources (e.g., using a suffix array library that returns 0-indexed SA with an LCP implementation that expects 1-indexed) will cause incorrect results or out-of-bounds errors. Always explicitly document and verify the convention used: is LCP[i] the lcp of SA[i] and SA[i-1] or SA[i] and SA[i+1]?

Another common error is failing to handle the sentinel character correctly. If the suffix array was built with an appended terminator '$', the LCP computation must account for it. The terminator ensures no suffix is a prefix of another, but if the LCP code compares past the terminator or treats it as a regular character, it may overcount. Similarly, forgetting to handle the case where rank[i] == 0 (the suffix is first in sorted order and has no predecessor) will lead to accessing SA[-1]. The Kasai loop must explicitly skip this case and reset k=0.

A performance-related mistake is not reusing the k value correctly in Kasai's algorithm. Resetting k=0 at the start of each iteration degrades the algorithm to O(n^2) worst-case, losing its linear guarantee. The correct pattern is if k > 0: k -= 1 at the end of each iteration. Another inefficiency is using Python string slicing s[i:] inside the comparison loop, which creates new string objects and is O(n) per slice. Always compare characters via indexing s[i+k] rather than slicing.

Best practices include thorough testing with edge cases: empty string, single character, all identical characters ("aaaaa"), all distinct characters ("abcde"), and known examples like "banana" and "abracadabra" where the expected SA and LCP can be manually verified. Using property-based testing (e.g., comparing Kasai output to naive output on random strings) is an excellent way to catch bugs. For production code, consider using established libraries for suffix array construction rather than rolling your own, as efficient SA construction is non-trivial to implement correctly and efficiently.

Code Robustness and Readability

Write code that is explicit about types and bounds. In Python, ensure the input is a string or list of integers (for integer alphabets) and handle Unicode correctly if needed. Add assertions to check that len(sa) == len(s) and that sa is a permutation of range(n). Document whether the function expects the suffix array to include the sentinel or not. For readability, use descriptive variable names like rank and lcp rather than single letters, and add comments explaining the amortized analysis trick. Finally, when building RMQ structures, be careful with inclusive vs exclusive interval boundaries in queries, as this is another frequent source of off-by-one errors.

10. Interview Questions

Understanding the LCP array is a strong signal in technical interviews for roles involving algorithms, bioinformatics, or systems programming. Interviewers often use it to test knowledge of advanced string algorithms, amortized analysis, and the ability to connect data structures to applications. Below are common questions and how to approach them.

Question 1: How do you find the longest repeated substring in O(n log n) time?

Answer Approach: Explain that the longest repeated substring corresponds to the maximum value in the LCP array. The reasoning is that any repeated substring must be a prefix of two suffixes, and those suffixes will be adjacent somewhere in the suffix array's sorted order (or more precisely, the maximum LCP among all adjacent pairs in the sorted order will be the answer). Steps: 1) Build suffix array O(n log n) using doubling or library sort, 2) Build LCP array O(n) using Kasai, 3) Find max(LCP) and its index idx, answer is s[SA[idx] : SA[idx] + max]. Mention that this finds one longest repeated substring; if there are multiple with same length, all indices where LCP equals max are answers. Complexity is dominated by SA construction.

Question 2: Explain why Kasai's algorithm is O(n) even though it has a nested while loop.

Answer Approach: This tests understanding of amortized analysis. Walk through the behavior of k. The outer loop runs n times. The inner while loop increments k only on successful character matches. Each successful match increases k by 1, and k is decreased by at most 1 per outer iteration. Since k never exceeds n and starts at 0, the total number of increments across the entire execution is at most n. Therefore, the total number of iterations of the inner loop is O(n), not O(n^2). This is similar to the analysis of the KMP algorithm's prefix function. Emphasize that the key is that k is not reset to zero each time.

Question 3: Given two strings A and B, how would you find their longest common substring using suffix array and LCP?

Answer Approach: Describe the concatenation trick. Create a new string S = A + '#' + B + '$' where '#' and '$' are separators smaller than any character and distinct from each other. Build SA and LCP for S. Then iterate over the LCP array and consider only adjacent pairs where one suffix comes from A and the other from B (i.e., SA[i] < len(A) and SA[i-1] > len(A) or vice versa). The maximum LCP among those cross-boundary pairs is the length of the longest common substring. To retrieve the substring, take S[SA[i] : SA[i] + max]. Complexity is O((n+m) log (n+m)). Mention alternative using suffix automaton or suffix tree, but SA+LCP is often simpler to implement.

Question 4: How many distinct substrings does a string have? Derive the formula using LCP.

Answer Approach: The total number of substrings (including duplicates) is n*(n+1)/2, which is the sum over all suffixes of their lengths. However, many substrings are repeated. When suffixes are sorted, the LCP array tells us how many prefixes are shared between consecutive suffixes. Specifically, suffix SA[i] contributes (n - SA[i]) - LCP[i] new distinct substrings that were not already counted by previous suffixes. Summing this gives distinct = n*(n+1)/2 - sum(LCP). Provide example with "banana" (n=6, total=21, sum LCP=1+3+0+0+2=6, distinct=15). This demonstrates understanding of how LCP quantifies duplication.

Question 5: What is the difference between the LCP array and the PLCP array, and why would you use PLCP?

Answer Approach: Define both: LCP is in suffix array order (LCP[i] = lcp of SA[i] and SA[i-1]), PLCP is in text order (PLCP[i] = LCP[rank[i]]). PLCP is a permutation of LCP. The advantage of PLCP is that it is more compressible and cache-friendly. Since PLCP values for consecutive i differ by at most 1 (PLCP[i] >= PLCP[i-1]-1 is not true, but the Kasai property implies PLCP is somewhat structured), the differential array PLCP[i] - PLCP[i-1] is small and can be encoded with fewer bits. Also, accessing PLCP sequentially matches the string's order, improving locality. In external memory settings, PLCP can be constructed and stored more efficiently. This question tests knowledge of variants and systems considerations.