Suffix Array and Suffix Tree in Data Structures & Applications

Suffix Arrays and Suffix Trees are powerful data structures used for efficient string processing, pattern matching, and text analysis. Both represent all suffixes of a given string but offer different trade‑offs in terms of construction time, memory usage, and query efficiency.

What is a Suffix Array?

A Suffix Array is a sorted array of all suffixes of a string. Instead of storing the actual suffixes (which would be memory‑intensive), it stores the starting indices of the suffixes in sorted lexicographical order.

String: "banana"
Suffixes:
0: banana
1: anana
2: nana
3: ana
4: na
5: a

Sorted suffixes:
5: a
3: ana
1: anana
0: banana
4: na
2: nana

Suffix Array: [5, 3, 1, 0, 4, 2]

Suffix Array Construction (Naïve)

def build_suffix_array(s):
    suffixes = [(s[i:], i) for i in range(len(s))]
    suffixes.sort()
    return [idx for _, idx in suffixes]

s = "banana"
print(build_suffix_array(s))  # Output: [5, 3, 1, 0, 4, 2]

Efficient Construction (Manber-Myers Algorithm)

def build_suffix_array_manber_myers(s):
    """
    O(n log n) construction using prefix doubling.
    Returns suffix array sorted lexicographically.
    """
    n = len(s)
    suffixes = list(range(n))
    rank = [ord(c) for c in s] + [-1]  # Initial ranks
    k = 1

    while k < n:
        suffixes.sort(key=lambda x: (rank[x], rank[x + k] if x + k < n else -1))
        new_rank = [0] * n
        for i in range(1, n):
            prev = suffixes[i - 1]
            curr = suffixes[i]
            if (rank[prev], rank[prev + k] if prev + k < n else -1) != \
               (rank[curr], rank[curr + k] if curr + k < n else -1):
                new_rank[curr] = new_rank[prev] + 1
            else:
                new_rank[curr] = new_rank[prev]
        rank = new_rank
        k *= 2

    return suffixes

s = "banana"
print(build_suffix_array_manber_myers(s))  # Output: [5, 3, 1, 0, 4, 2]

What is a Suffix Tree?

A Suffix Tree is a compressed trie (prefix tree) of all suffixes of a string. Each edge is labeled with a substring, and every suffix corresponds to a path from the root to a leaf. It enables extremely fast pattern matching (O(m) where m is the pattern length) but is more memory‑intensive than a suffix array.

Key Properties of a Suffix Tree

• Each internal node has at least two children.
• Edges are labeled with non‑empty substrings.
• No two edges from the same node have labels starting with the same character.
• Each leaf represents a suffix of the original string.

Suffix Array vs Suffix Tree

Longest Common Prefix (LCP) Array

An LCP (Longest Common Prefix) array stores the length of the longest common prefix between consecutive suffixes in the suffix array. It is essential for many suffix array applications.

def build_lcp_array(s, suffix_arr):
    n = len(s)
    rank = [0] * n
    for i in range(n):
        rank[suffix_arr[i]] = i

    lcp = [0] * (n - 1)
    k = 0
    for i in range(n):
        if rank[i] == n - 1:
            k = 0
            continue
        j = suffix_arr[rank[i] + 1]
        while i + k < n and j + k < n and s[i + k] == s[j + k]:
            k += 1
        lcp[rank[i]] = k
        if k:
            k -= 1
    return lcp

s = "banana"
suffix_arr = build_suffix_array(s)
print(build_lcp_array(s, suffix_arr))  # Output: [1, 3, 0, 0, 2]

Applications

1. Pattern Matching

Find all occurrences of a pattern in a text efficiently.

def search_pattern(text, pattern):
    suffix_arr = build_suffix_array(text)
    # Binary search on suffix array
    low, high = 0, len(suffix_arr) - 1
    while low <= high:
        mid = (low + high) // 2
        suffix = text[suffix_arr[mid]:]
        if suffix.startswith(pattern):
            # Find all matching occurrences
            occurrences = []
            idx = mid
            while idx >= 0 and text[suffix_arr[idx]:].startswith(pattern):
                occurrences.append(suffix_arr[idx])
                idx -= 1
            idx = mid + 1
            while idx < len(suffix_arr) and text[suffix_arr[idx]:].startswith(pattern):
                occurrences.append(suffix_arr[idx])
                idx += 1
            return sorted(occurrences)
        elif pattern < suffix:
            high = mid - 1
        else:
            low = mid + 1
    return []

2. Longest Repeated Substring

Find the longest substring that occurs at least twice.

def longest_repeated_substring(s):
    suffix_arr = build_suffix_array(s)
    lcp = build_lcp_array(s, suffix_arr)
    max_lcp = max(lcp) if lcp else 0
    idx = lcp.index(max_lcp) if max_lcp else -1
    if idx != -1:
        return s[suffix_arr[idx]:suffix_arr[idx] + max_lcp]
    return ""

3. Longest Common Substring

Find the longest common substring between two strings.

def longest_common_substring(s1, s2):
    # Concatenate with a unique separator
    combined = s1 + "$" + s2 + "#"
    suffix_arr = build_suffix_array(combined)
    lcp = build_lcp_array(combined, suffix_arr)
    # Find max LCP where suffixes belong to different strings
    max_len = 0
    for i in range(len(lcp)):
        if (suffix_arr[i] < len(s1) and suffix_arr[i + 1] > len(s1)) or \
           (suffix_arr[i] > len(s1) and suffix_arr[i + 1] < len(s1)):
            max_len = max(max_len, lcp[i])
    return max_len

4. Bioinformatics Applications

• Genome Assembly: Finding overlapping reads.
• DNA Sequence Analysis: Identifying repeated patterns.
• Multiple Sequence Alignment: Finding common subsequences.

5. Other Applications

• Data Compression: Identifying repeated substrings for compression algorithms.
• Plagiarism Detection: Finding common substrings in documents.
• Spell Checking: Efficient dictionary lookups.
• Full‑Text Search Engines: Indexing and searching large text corpora.

Complexity Summary

Key Takeaways

• Suffix Arrays are simpler, more memory‑efficient, and easier to implement.
• Suffix Trees provide faster pattern matching and more powerful queries but are more complex.
• Many applications (like those in bioinformatics and text processing) benefit from either structure.
• The LCP array extends suffix arrays to support many of the same operations as suffix trees.