Suffix Arrays: Construction, LCP, and Applications

---

What is a Suffix Array?

A suffix array is a sorted array of all suffixes of a string, represented by their starting indices.

For S = "banana$":

Suffix	Starting Index
banana$	0
anana$	1
nana$	2
ana$	3
na$	4
a$	5
$	6

After sorting alphabetically:

Rank	Suffix	SA Value
0	$	6
1	a$	5
2	ana$	3
3	anana$	1
4	banana$	0
5	na$	4
6	nana$	2

Suffix Array = [6, 5, 3, 1, 0, 4, 2]

The $ sentinel character ensures no suffix is a prefix of another (important for correctness).

---

Naive Construction: O(n^2 log n)

The simplest approach: generate all suffixes, sort them.

def suffix_array_naive(s):
    """Build suffix array by sorting all suffixes. O(n^2 log 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]


s = "banana$"
sa = suffix_array_naive(s)
print(f"Suffix Array: {sa}")
# Suffix Array: [6, 5, 3, 1, 0, 4, 2]

# Print sorted suffixes
for rank, idx in enumerate(sa):
    print(f"  SA[{rank}] = {idx}: {s[idx:]}")

This is O(n^2 log n) because sorting n strings of average length n/2 takes O(n * n * log n) in the worst case (each comparison is O(n)).

---

Efficient Construction: O(n log^2 n)

The key idea: sort suffixes by their first 2^k characters, doubling k each round. We use the rank from the previous round to compare in O(1) instead of O(n).

def suffix_array_efficient(s):
    """
    Build suffix array in O(n log^2 n) using prefix doubling.
    Each sorting round uses O(n log n) with built-in sort.
    """
    n = len(s)
    
    # Initial ranking: by single character
    sa = list(range(n))
    rank = [ord(c) for c in s]
    tmp = [0] * n
    
    k = 1  # Current comparison length
    while k < n:
        # Sort by (rank[i], rank[i + k])
        # Using the pair as a sort key
        def sort_key(i):
            return (rank[i], rank[i + k] if i + k < n else -1)
        
        sa.sort(key=sort_key)
        
        # Compute new ranks
        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i - 1]]
            if sort_key(sa[i]) != sort_key(sa[i - 1]):
                tmp[sa[i]] += 1
        
        rank = tmp[:]
        
        # If all ranks are unique, we're done
        if rank[sa[-1]] == n - 1:
            break
        
        k *= 2
    
    return sa


s = "banana$"
sa = suffix_array_efficient(s)
print(f"Suffix Array: {sa}")
# Suffix Array: [6, 5, 3, 1, 0, 4, 2]

How Prefix Doubling Works

• Round 0 (k=1): Sort by first character.
• Round 1 (k=2): Sort by first 2 characters. Use rank from round 0 to compare pairs.
• Round 2 (k=4): Sort by first 4 characters.
• …
• Round log n: All suffixes are fully compared.

Each round takes O(n log n) for sorting, and there are O(log n) rounds, giving O(n log^2 n) total.

With radix sort instead of comparison sort, each round becomes O(n), giving O(n log n) total.

---

O(n log n) Construction with Radix Sort

def suffix_array_nlogn(s):
    """Build suffix array in O(n log n) using radix sort."""
    n = len(s)
    
    sa = list(range(n))
    rank = [ord(c) for c in s]
    tmp = [0] * n
    
    def radix_sort():
        """Stable sort sa by (rank[sa[i]], rank[sa[i]+k]) using counting sort."""
        # Sort by second key first (rank[i + k])
        count = [0] * (max(max(rank) + 2, n + 1))
        
        # Sort by second component
        for i in range(n):
            key = rank[sa[i] + k] + 1 if sa[i] + k < n else 0
            count[key] += 1
        for i in range(1, len(count)):
            count[i] += count[i - 1]
        
        buf = [0] * n
        for i in range(n - 1, -1, -1):
            key = rank[sa[i] + k] + 1 if sa[i] + k < n else 0
            count[key] -= 1
            buf[count[key]] = sa[i]
        
        # Sort by first component (stable, preserves second order)
        count2 = [0] * (max(rank) + 2)
        for i in range(n):
            count2[rank[buf[i]] + 1] += 1
        for i in range(1, len(count2)):
            count2[i] += count2[i - 1]
        
        for i in range(n - 1, -1, -1):
            count2[rank[buf[i]] + 1] -= 1
            sa[count2[rank[buf[i]] + 1]] = buf[i]
    
    k = 1
    while k < n:
        radix_sort()
        
        tmp[sa[0]] = 0
        for i in range(1, n):
            prev_pair = (rank[sa[i-1]], rank[sa[i-1]+k] if sa[i-1]+k < n else -1)
            curr_pair = (rank[sa[i]], rank[sa[i]+k] if sa[i]+k < n else -1)
            tmp[sa[i]] = tmp[sa[i-1]] + (1 if curr_pair != prev_pair else 0)
        
        rank = tmp[:]
        if rank[sa[-1]] == n - 1:
            break
        k *= 2
    
    return sa


s = "banana$"
sa = suffix_array_nlogn(s)
print(f"Suffix Array: {sa}")

---

LCP Array: Longest Common Prefix

The LCP array stores the length of the longest common prefix between consecutive suffixes in the sorted order.

LCP[i] = length of the longest common prefix of SA[i-1] and SA[i].

Kasai’s Algorithm: O(n)

Kasai’s algorithm computes the LCP array in O(n) by exploiting the fact that if we know LCP for suffix starting at i, then the LCP for suffix starting at i+1 is at least LCP - 1.

def build_lcp_array(s, sa):
    """Compute LCP array using Kasai's algorithm in O(n)."""
    n = len(s)
    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 rank[i] == 0:
            k = 0
            continue
        
        # Compare suffix at i with the previous one in sorted order
        j = sa[rank[i] - 1]
        
        while i + k < n and j + k < n and s[i + k] == s[j + k]:
            k += 1
        
        lcp[rank[i]] = k
        
        # Key insight: when moving to next suffix (i+1),
        # the LCP can decrease by at most 1
        if k > 0:
            k -= 1
    
    return lcp


s = "banana$"
sa = suffix_array_efficient(s)
lcp = build_lcp_array(s, sa)

print("Rank | SA | LCP | Suffix")
print("-----|------|-----|-------")
for i in range(len(sa)):
    print(f"  {i}  |  {sa[i]}   |  {lcp[i]}  | {s[sa[i]:]}")

Output:

Rank | SA | LCP | Suffix
-----|------|-----|-------
  0  |  6   |  0  | $
  1  |  5   |  0  | a$
  2  |  3   |  1  | ana$
  3  |  1   |  3  | anana$
  4  |  0   |  0  | banana$
  5  |  4   |  0  | na$
  6  |  2   |  2  | nana$

---

Pattern Searching with Suffix Array

To find all occurrences of a pattern P in text S, use binary search on the suffix array. Since the suffixes are sorted, all matches form a contiguous range.

def search_pattern(s, sa, pattern):
    """Find all occurrences of pattern in s using binary search on SA."""
    n = len(s)
    m = len(pattern)
    
    # Find leftmost match (lower bound)
    lo, hi = 0, n - 1
    left = n  # Default: not found
    while lo <= hi:
        mid = (lo + hi) // 2
        suffix = s[sa[mid]:sa[mid] + m]
        if suffix >= pattern:
            left = mid
            hi = mid - 1
        else:
            lo = mid + 1
    
    # Check if we actually found a match
    if left >= n or s[sa[left]:sa[left] + m] != pattern:
        return []
    
    # Find rightmost match (upper bound)
    lo, hi = left, n - 1
    right = left
    while lo <= hi:
        mid = (lo + hi) // 2
        suffix = s[sa[mid]:sa[mid] + m]
        if suffix <= pattern:
            right = mid
            lo = mid + 1
        else:
            hi = mid - 1
    
    # All matches are in SA[left..right]
    return sorted([sa[i] for i in range(left, right + 1)])


s = "banana$"
sa = suffix_array_efficient(s)

print(search_pattern(s, sa, "an"))    # [1, 3]
print(search_pattern(s, sa, "na"))    # [2, 4]
print(search_pattern(s, sa, "ban"))   # [0]
print(search_pattern(s, sa, "xyz"))   # []

Time complexity: O(m log n) per search (binary search with O(m) string comparison at each step).

---

Application: Longest Repeated Substring

The longest substring that appears at least twice is found by taking the maximum value in the LCP array.

def longest_repeated_substring(s):
    """Find the longest substring appearing at least twice."""
    sa = suffix_array_efficient(s)
    lcp = build_lcp_array(s, sa)
    
    max_lcp = 0
    best_idx = -1
    
    for i in range(1, len(lcp)):
        if lcp[i] > max_lcp:
            max_lcp = lcp[i]
            best_idx = sa[i]
    
    if max_lcp == 0:
        return ""
    
    return s[best_idx:best_idx + max_lcp]


print(longest_repeated_substring("banana"))    # "ana"
print(longest_repeated_substring("abcabc"))    # "abc"
print(longest_repeated_substring("abcdef"))    # ""
print(longest_repeated_substring("aabaaab"))   # "aab"

---

Application: Number of Distinct Substrings

Total substrings = n(n+1)/2. Subtract the LCP values (which count duplicate prefixes between adjacent sorted suffixes):

def count_distinct_substrings(s):
    """Count the number of distinct substrings of s."""
    n = len(s)
    sa = suffix_array_efficient(s)
    lcp = build_lcp_array(s, sa)
    
    total = n * (n + 1) // 2
    duplicates = sum(lcp)
    
    return total - duplicates


print(count_distinct_substrings("banana"))   # 15
print(count_distinct_substrings("abc"))      # 6
print(count_distinct_substrings("aab"))      # 5

---

Application: Longest Common Substring of Two Strings

Concatenate the two strings with a separator, build the suffix array and LCP array, then find the maximum LCP between suffixes from different strings:

def longest_common_substring(s1, s2):
    """Find the longest common substring of s1 and s2."""
    n1 = len(s1)
    # Use a separator that doesn't appear in either string
    combined = s1 + "#" + s2 + "$"
    n = len(combined)
    
    sa = suffix_array_efficient(combined)
    lcp = build_lcp_array(combined, sa)
    
    best = 0
    best_idx = -1
    
    for i in range(1, n):
        # Check if adjacent suffixes come from different strings
        from_s1_prev = sa[i - 1] < n1
        from_s1_curr = sa[i] < n1
        
        if from_s1_prev != from_s1_curr and lcp[i] > best:
            best = lcp[i]
            best_idx = sa[i]
    
    if best == 0:
        return ""
    return combined[best_idx:best_idx + best]


print(longest_common_substring("abcdef", "zbcdf"))    # "bcd"
print(longest_common_substring("dynamic", "dynamic")) # "dynamic"
print(longest_common_substring("abc", "xyz"))          # ""

---

Suffix Array vs Suffix Tree

Feature	Suffix Array	Suffix Tree
Space	O(n)	O(n) but large constant
Build time	O(n log n) or O(n)	O(n) with Ukkonen’s
Pattern search	O(m log n)	O(m)
Implementation	Simpler	Complex
LCP computation	O(n) with Kasai’s	Built into tree
Practical performance	Better cache locality	More pointer chasing

Suffix arrays are preferred in practice for competitive programming due to simpler implementation and better memory characteristics.

---

Complete Reusable Class

class SuffixArray:
    """Complete suffix array with LCP and common operations."""
    
    def __init__(self, s):
        self.s = s
        self.n = len(s)
        self.sa = self._build()
        self.rank = [0] * self.n
        for i in range(self.n):
            self.rank[self.sa[i]] = i
        self.lcp = self._build_lcp()
    
    def _build(self):
        n = self.n
        sa = list(range(n))
        rank = [ord(c) for c in self.s]
        tmp = [0] * n
        
        k = 1
        while k < n:
            def key(i):
                return (rank[i], rank[i + k] if i + k < n else -1)
            
            sa.sort(key=key)
            tmp[sa[0]] = 0
            for i in range(1, n):
                tmp[sa[i]] = tmp[sa[i-1]] + (1 if key(sa[i]) != key(sa[i-1]) else 0)
            rank = tmp[:]
            if rank[sa[-1]] == n - 1:
                break
            k *= 2
        
        return sa
    
    def _build_lcp(self):
        lcp = [0] * self.n
        k = 0
        for i in range(self.n):
            if self.rank[i] == 0:
                k = 0
                continue
            j = self.sa[self.rank[i] - 1]
            while (i + k < self.n and j + k < self.n 
                   and self.s[i + k] == self.s[j + k]):
                k += 1
            lcp[self.rank[i]] = k
            if k > 0:
                k -= 1
        return lcp
    
    def search(self, pattern):
        """Find all occurrences of pattern."""
        m = len(pattern)
        lo, hi = 0, self.n - 1
        left = self.n
        while lo <= hi:
            mid = (lo + hi) // 2
            if self.s[self.sa[mid]:self.sa[mid]+m] >= pattern:
                left = mid
                hi = mid - 1
            else:
                lo = mid + 1
        
        if left >= self.n or self.s[self.sa[left]:self.sa[left]+m] != pattern:
            return []
        
        lo, hi = left, self.n - 1
        right = left
        while lo <= hi:
            mid = (lo + hi) // 2
            if self.s[self.sa[mid]:self.sa[mid]+m] <= pattern:
                right = mid
                lo = mid + 1
            else:
                hi = mid - 1
        
        return sorted(self.sa[left:right+1])
    
    def longest_repeated(self):
        max_l = max(self.lcp) if self.lcp else 0
        if max_l == 0:
            return ""
        idx = self.lcp.index(max_l)
        return self.s[self.sa[idx]:self.sa[idx]+max_l]
    
    def distinct_substring_count(self):
        return self.n * (self.n + 1) // 2 - sum(self.lcp)


# Usage
sa = SuffixArray("banana")
print(f"SA: {sa.sa}")
print(f"LCP: {sa.lcp}")
print(f"Search 'an': {sa.search('an')}")
print(f"Longest repeated: {sa.longest_repeated()}")
print(f"Distinct substrings: {sa.distinct_substring_count()}")

---

Practice Problems

1. Suffix Array (SPOJ SARRAY) — Build a suffix array for a given string.
2. Longest Common Substring (SPOJ LCS) — Two strings, find LCS using suffix array.
3. Distinct Substrings (SPOJ DISUBSTR) — Count distinct substrings using SA + LCP.
4. Longest Repeated Substring — max(LCP array).
5. String Matching (CSES) — Find all occurrences of pattern using SA + binary search.
6. Longest Common Substring of K Strings — Generalize with binary search on answer + SA.

---

Key Takeaways

• A suffix array is a space-efficient alternative to suffix trees, storing sorted suffix indices.
• O(n log^2 n) construction with prefix doubling is practical; O(n log n) is achievable with radix sort.
• Kasai’s algorithm builds the LCP array in O(n), leveraging the “LCP decreases by at most 1” property.
• Pattern search takes O(m log n) using binary search on the sorted suffix array.
• The LCP array unlocks powerful applications: longest repeated substring, distinct substring count, and longest common substring.