Suffix arrays in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the basic structure of suffix arrays

What does a suffix array represent for a given string?

A An array of all suffixes of the string sorted in lexicographical order, represented by their starting indices.

B An array containing the frequency of each character in the string.

C An array of all prefixes of the string sorted by length.

D An array of the string's characters sorted alphabetically.

💡 Hint

Think about how suffixes are organized to help with substring searches.

A suffix array stores the starting positions of all suffixes of a string sorted lexicographically. This helps in efficient substring search and pattern matching.

📋 Factual

intermediate

Suffix array construction time complexity

What is the best known time complexity for constructing a suffix array for a string of length n?

A O(n log n)

B O(n)

C O(n^2)

D O(log n)

💡 Hint

Modern algorithms can build suffix arrays very efficiently.

There exist algorithms like SA-IS that can construct suffix arrays in linear time O(n), which is optimal for this problem.

🚀 Application

advanced

Using suffix arrays for substring search

Given a suffix array for a string, how can you efficiently check if a substring exists in the string?

A Perform a binary search on the suffix array comparing the substring with suffixes starting at indices stored in the array.

B Scan the entire string from start to end to find the substring.

C Sort the characters of the substring and compare with sorted characters of the string.

D Use the suffix array to count character frequencies and infer substring presence.

💡 Hint

Think about how the suffix array is sorted and how binary search works.

Since suffixes are sorted lexicographically in the suffix array, binary search can quickly find if the substring matches the prefix of any suffix.

🔍 Analysis

advanced

Comparing suffix arrays and suffix trees

Which of the following is a key advantage of suffix arrays over suffix trees?

A Suffix arrays allow faster substring search than suffix trees.

B Suffix arrays are always faster to build than suffix trees.

C Suffix arrays can represent all substrings explicitly, unlike suffix trees.

D Suffix arrays use less memory and are simpler to implement than suffix trees.

💡 Hint

Consider memory usage and implementation complexity.

Suffix arrays are more space-efficient and simpler to implement compared to suffix trees, though suffix trees can offer faster queries in some cases.

❓ Reasoning

expert

Determining the number of distinct substrings using suffix arrays

Given a string of length n and its suffix array along with the longest common prefix (LCP) array, how can you compute the number of distinct substrings of the string?

A Number of suffixes minus the maximum LCP value.

B Sum of all LCP values only.

C Sum of lengths of all suffixes minus the sum of all LCP values.

D Length of the string multiplied by the number of suffixes.

💡 Hint

Think about how suffixes overlap and how LCP helps avoid counting duplicates.

The total number of substrings is the sum of lengths of all suffixes. Subtracting the sum of LCP values removes duplicates counted due to common prefixes.

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