Suffix arrays in Data Structures Theory - Full Explanation

Introduction

Imagine you want to quickly find if a word or pattern appears inside a long text. Searching every time from the start can be slow. Suffix arrays help solve this by organizing all possible endings of the text in a way that makes searching fast and easy.

Explanation

What is a suffix

A suffix is a part of a string that starts at any position and goes to the end. For example, in the word 'banana', 'nana' and 'a' are suffixes. Every string has as many suffixes as its length.

A suffix is a substring that begins at some position and continues to the end of the string.

Structure of a suffix array

A suffix array is a list of all suffixes of a string, sorted in alphabetical order. Instead of storing the suffixes themselves, it stores the starting positions of these suffixes in the original string. This makes it compact and efficient.

A suffix array stores the starting indexes of all suffixes sorted lexicographically.

How suffix arrays help searching

Because suffixes are sorted, you can use binary search to quickly find if a pattern exists in the text. This is much faster than checking every position one by one. It works like looking up a word in a dictionary.

Sorted suffixes allow fast pattern search using binary search.

Building suffix arrays

Creating a suffix array involves listing all suffixes and sorting them. Naively, this can be slow, but there are efficient algorithms that build suffix arrays quickly even for large texts. These algorithms use clever tricks to avoid repeated comparisons.

Efficient algorithms exist to build suffix arrays quickly for large strings.

Applications of suffix arrays

Suffix arrays are used in text search engines, DNA sequence analysis, and data compression. They help find repeated patterns, match sequences, and speed up many string-related tasks.

Suffix arrays are powerful tools for fast text and pattern matching in many fields.

Real World Analogy

Imagine a library where every book is opened at every possible page, and each page is listed in alphabetical order by its first sentence. To find a phrase, you just look it up in this sorted list instead of flipping through every book.

Suffix → A page in a book starting from a certain point to the end

Suffix array → A sorted catalog listing all pages by their first sentence

Binary search on suffix array → Looking up a phrase quickly in the catalog instead of reading every page

Building suffix arrays → Organizing and sorting all pages in the catalog efficiently

Applications → Using the catalog to find information quickly in libraries, DNA labs, or data centers

Diagram

Diagram

Original string: banana

Suffixes and their start positions:
0: banana
1: anana
2: nana
3: ana
4: na
5: a

Sorted suffixes (suffix array):
5: a
3: ana
1: anana
0: banana
4: na
2: nana

This diagram shows the original string, all its suffixes with their start positions, and the suffix array listing these positions sorted by suffix.

Key Facts

Suffix → A substring starting at any position and extending to the end of the string.

Suffix array → An array of starting indexes of all suffixes sorted in lexicographical order.

Binary search → A fast search method that works on sorted data by repeatedly dividing the search interval in half.

Suffix array construction → The process of creating a suffix array, which can be done efficiently with specialized algorithms.

Applications of suffix arrays → Used in text search, DNA analysis, and data compression for fast pattern matching.

Code Example

Data Structures Theory

def build_suffix_array(s: str) -> list[int]:
    return sorted(range(len(s)), key=lambda i: s[i:])

text = "banana"
suffix_array = build_suffix_array(text)
print(suffix_array)

Common Confusions

Suffix arrays store the suffix strings themselves.

Suffix arrays store the suffix strings themselves. Suffix arrays store only the starting positions of suffixes, not the suffix strings, to save space.

Suffix arrays are the same as suffix trees.

Suffix arrays are the same as suffix trees. Suffix arrays are simpler, space-efficient arrays of indexes, while suffix trees are complex tree structures; both help with string search but differ in design.

Building suffix arrays is always slow because it involves sorting many suffixes.

Building suffix arrays is always slow because it involves sorting many suffixes. Special algorithms build suffix arrays efficiently without sorting all suffixes directly, making it fast even for large texts.

Summary

Suffix arrays organize all endings of a string in sorted order to enable fast searching.

They store starting positions of suffixes, not the suffixes themselves, saving space.

Efficient algorithms and binary search make suffix arrays practical for large texts.

Practice

1. What is a suffix array in the context of text processing?

easy

A. A data structure that stores the frequency of each character

B. An array listing all suffixes of a text sorted alphabetically

C. An array listing all prefixes of a text sorted by length

D. A list of all words in a text sorted by their length

Solution

1. Step 1: Understand suffix array definition

   A suffix array is a list of all suffixes (endings) of a text sorted alphabetically.

2. Step 2: Compare options with definition

   Only An array listing all suffixes of a text sorted alphabetically correctly describes this; others describe different concepts.

3. Final Answer:

   An array listing all suffixes of a text sorted alphabetically -> Option B

4. Quick Check:

   Suffix array = sorted suffixes list [OK]

Hint: Suffix arrays always sort text endings alphabetically [OK]

Common Mistakes:

• Confusing suffix array with prefix array
• Thinking it stores character frequencies
• Assuming it sorts words, not suffixes

2. Which of the following is the correct way to represent the suffix array of the string banana?

easy

A. [5, 3, 1, 0, 4, 2]

B. [0, 1, 2, 3, 4, 5]

C. [1, 3, 5, 0, 2, 4]

D. [5, 4, 3, 2, 1, 0]

Solution

1. Step 1: List all suffixes of 'banana' with their start indices

   Suffixes: 0:'banana', 1:'anana', 2:'nana', 3:'ana', 4:'na', 5:'a'

2. Step 2: Sort suffixes alphabetically and note indices

   Sorted suffixes: 'a'(5), 'ana'(3), 'anana'(1), 'banana'(0), 'na'(4), 'nana'(2)

3. Final Answer:

   [5, 3, 1, 0, 4, 2] -> Option A

4. Quick Check:

   Sorted suffix indices = [5,3,1,0,4,2] [OK]

Hint: Sort suffixes alphabetically, then list their start positions [OK]

Common Mistakes:

• Sorting indices instead of suffix strings
• Confusing prefix indices with suffix indices
• Reversing the order of suffixes

3. Given the suffix array [3, 0, 4, 1, 5, 2] for a string, what is the likely original string if the suffixes sorted alphabetically are ['ana', 'banana', 'na', 'anana', 'a', 'nana']?

medium

A. panama

B. bandana

C. cabana

D. banana

Solution

1. Step 1: Match suffixes to indices

   Suffixes: 'ana'(3), 'banana'(0), 'na'(4), 'anana'(1), 'a'(5), 'nana'(2)

2. Step 2: Reconstruct string from suffixes and indices

   Suffix starting at 0 is 'banana', so original string is 'banana'

3. Final Answer:

   banana -> Option D

4. Quick Check:

   Suffix array matches 'banana' suffixes [OK]

Hint: Match suffix indices to strings to find original text [OK]

Common Mistakes:

• Assuming suffix array directly shows original string
• Mixing up suffix order with original string order
• Ignoring suffix start positions

4. Identify the error in the following suffix array construction code snippet for string "apple":

suffixes = [s[i:] for i in range(len(s))]
suffixes.sort()
suffix_array = [s.index(suf) for suf in suffixes]

medium

A. Using s.index() can return wrong indices if suffixes repeat

B. The suffixes list is not sorted correctly

C. Range should start from 1, not 0

D. The code misses converting suffixes to tuples before sorting

Solution

1. Step 1: Understand s.index() behavior

   s.index() returns the first occurrence index of substring, which can be wrong if suffix repeats.

2. Step 2: Identify impact on suffix array

   If suffixes repeat, s.index() returns same index multiple times, causing incorrect suffix array.

3. Final Answer:

   Using s.index() can return wrong indices if suffixes repeat -> Option A

4. Quick Check:

   Repeated suffixes break s.index() correctness [OK]

Hint: Avoid s.index() for suffix positions; use loop index instead [OK]

Common Mistakes:

• Assuming s.index() always gives correct suffix start
• Not sorting suffixes before indexing
• Starting range incorrectly

5. You want to find all occurrences of the pattern "ana" in the text "banana" using its suffix array [5, 3, 1, 0, 4, 2]. Which approach correctly uses the suffix array for this search?

hard

A. Sort the pattern 'ana' and compare with sorted suffixes

B. Scan the original text linearly and check each character for 'ana'

C. Perform a binary search on suffix array indices comparing suffixes with 'ana' to find matches

D. Use the suffix array to count characters in the text

Solution

1. Step 1: Understand suffix array usage for pattern search

   Suffix arrays allow binary search on sorted suffixes to quickly find pattern matches.

2. Step 2: Evaluate options

   Perform a binary search on suffix array indices comparing suffixes with 'ana' to find matches correctly describes binary search on suffix array; others do not use suffix array properly.

3. Final Answer:

   Perform a binary search on suffix array indices comparing suffixes with 'ana' to find matches -> Option C

4. Quick Check:

   Binary search on suffix array = efficient pattern search [OK]

Hint: Use binary search on suffix array for fast pattern matching [OK]

Common Mistakes:

• Linear scan ignoring suffix array benefits
• Sorting pattern instead of suffixes
• Using suffix array for unrelated tasks