Suffix arrays in Data Structures Theory - Step-by-Step Execution

Concept Flow - Suffix arrays

Input String S

↓

Generate all suffixes of S

↓

Sort suffixes lexicographically

↓

Store starting indices of sorted suffixes

↓

Suffix Array constructed

↓

Use suffix array for fast substring queries

Start with the input string, list all suffixes, sort them alphabetically, then record their starting positions to form the suffix array.

Execution Sample

Data Structures Theory

S = "banana"
suffixes = [(S[i:], i) for i in range(len(S))]
suffixes.sort()
suffix_array = [pos for (suf, pos) in suffixes]
print(suffix_array)

This code creates all suffixes of "banana", sorts them, and prints the array of starting indices in sorted order.

Analysis Table

Step	Operation	Suffix Generated	Suffix Index	Suffixes Sorted So Far	Suffix Array State
1	Generate suffix	banana	0	[('banana',0)]	[]
2	Generate suffix	anana	1	[('banana',0), ('anana',1)]	[]
3	Generate suffix	nana	2	[('banana',0), ('anana',1), ('nana',2)]	[]
4	Generate suffix	ana	3	[('banana',0), ('anana',1), ('nana',2), ('ana',3)]	[]
5	Generate suffix	na	4	[('banana',0), ('anana',1), ('nana',2), ('ana',3), ('na',4)]	[]
6	Generate suffix	a	5	[('banana',0), ('anana',1), ('nana',2), ('ana',3), ('na',4), ('a',5)]	[]
7	Sort suffixes lex order	-	-	[('a',5), ('ana',3), ('anana',1), ('banana',0), ('na',4), ('nana',2)]	[]
8	Extract indices	-	-	-	[5, 3, 1, 0, 4, 2]
9	Print suffix array	-	-	-	[5, 3, 1, 0, 4, 2]

💡 All suffixes generated and sorted; suffix array completed with starting indices.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
S	"banana"	"banana"	"banana"	"banana"	"banana"	"banana"	"banana"	"banana"	"banana"	"banana"
suffixes	[]	[('banana',0)]	[('banana',0), ('anana',1)]	[('banana',0), ('anana',1), ('nana',2)]	[('banana',0), ('anana',1), ('nana',2), ('ana',3)]	[('banana',0), ('anana',1), ('nana',2), ('ana',3), ('na',4)]	[('banana',0), ('anana',1), ('nana',2), ('ana',3), ('na',4), ('a',5)]	[('a',5), ('ana',3), ('anana',1), ('banana',0), ('na',4), ('nana',2)]	[('a',5), ('ana',3), ('anana',1), ('banana',0), ('na',4), ('nana',2)]	[('a',5), ('ana',3), ('anana',1), ('banana',0), ('na',4), ('nana',2)]
suffix_array	[]	[]	[]	[]	[]	[]	[]	[]	[5, 3, 1, 0, 4, 2]	[5, 3, 1, 0, 4, 2]

Key Insights - 3 Insights

Why do we store the starting indices of suffixes instead of the suffix strings themselves?

Storing indices saves space and allows quick reference to the original string. The execution_table row 8 shows extracting indices after sorting suffixes.

Why must suffixes be sorted lexicographically?

Sorting suffixes alphabetically arranges all substrings in order, enabling fast search. See execution_table row 7 where suffixes are sorted.

How does the suffix array help in substring search?

Because suffixes are sorted, binary search on suffix_array indices quickly finds substrings. This is implied after the suffix array is built in execution_table row 9.

Visual Quiz - 3 Questions

Look at the execution_table at step 7. Which suffix is first in the sorted list?

A "banana" starting at index 0

B "a" starting at index 5

C "ana" starting at index 3

D "nana" starting at index 2

💡 Hint

Check the 'Suffixes Sorted So Far' column at step 7 in execution_table.

At which step does the suffix array get its final values?

A Step 8

B Step 7

C Step 6

D Step 9

💡 Hint

Look at the 'Suffix Array State' column in execution_table to see when indices are extracted.

If the input string was "apple", how many suffixes would be generated?

A 4

B 6

C 5

D 7

💡 Hint

Refer to variable_tracker 'suffixes' length after all suffixes generated for "banana" which has length 6.

Concept Snapshot

Suffix arrays list all suffixes of a string.
They are sorted alphabetically.
We store the starting indices of these sorted suffixes.
This structure helps fast substring search.
Building suffix arrays involves generating suffixes, sorting, and indexing.

Full Transcript

Suffix arrays are built by taking all suffixes of a string, sorting them alphabetically, and recording their starting positions. For example, for the string 'banana', we generate suffixes like 'banana', 'anana', 'nana', 'ana', 'na', and 'a'. These suffixes are sorted lexicographically to get 'a', 'ana', 'anana', 'banana', 'na', 'nana'. We then create the suffix array by storing the starting indices of these sorted suffixes, resulting in [5, 3, 1, 0, 4, 2]. This array allows efficient substring searches by binary searching the suffixes. The process involves generating suffixes, sorting them, and extracting indices, as shown step-by-step in the execution table and variable tracker. Key points include why indices are stored instead of strings, the importance of sorting, and how the suffix array supports fast queries.

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