Suffix arrays in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a suffix array by sorting all suffixes of the string s.

Data Structures Theory

suffixes = [s[i:] for i in range(len(s))]
suffix_array = sorted([1])

Drag options to blanks, or click blank then click option'

Asuffixes

Bs

Crange(len(s))

Dsorted(s)

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting the string itself instead of suffixes.

Sorting the range of indices instead of suffixes.

The suffix array is created by sorting all suffixes of the string. Here, suffixes is the list of all suffixes, so sorting suffixes gives the suffix array.

2fill in blank

medium

Complete the code to build the suffix array as a list of starting indices of sorted suffixes.

Data Structures Theory

suffix_array = sorted(range(len(s)), key=lambda i: [1])

Drag options to blanks, or click blank then click option'

As

Bi

Clen(s)

Ds[i:]

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting indices without a key function.

Using the index i itself as the key.

The suffix array stores the starting indices of suffixes sorted lexicographically. The key function lambda i: s[i:] sorts indices by their suffixes.

3fill in blank

hard

Fix the error in the code that tries to build a suffix array but incorrectly sorts characters instead of suffixes.

Data Structures Theory

suffix_array = sorted(range(len(s)), key=lambda i: s[[1]])

Drag options to blanks, or click blank then click option'

Alen(s)

B0

Ci

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using a fixed index like 0 instead of i.

Using an index out of range like len(s).

The code sorts indices by the character at position i, which is correct to access the first character of each suffix. However, sorting by only one character is not a full suffix array. Still, the blank must be i to avoid errors.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension mapping each suffix to its starting index.

Data Structures Theory

{s[i:]: [1] for i in range([2])}

Drag options to blanks, or click blank then click option'

Ai

Blen(s)

C0

Ds

Attempts:

3 left

💡 Hint

Common Mistakes

Using the suffix string as the value instead of the index.

Using an incorrect range that misses suffixes.

The dictionary comprehension maps each suffix s[i:] to its starting index i. The range must go from 0 to len(s) to cover all suffixes.

5fill in blank

hard

Fill all three blanks to create a suffix array by sorting indices with a key function that returns suffixes.

Data Structures Theory

suffix_array = sorted(range([1]), key=lambda [2]: s[[3]:])

Drag options to blanks, or click blank then click option'

Alen(s)

Bi

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using a fixed number instead of len(s).

Using different variable names in lambda and slice.

Using 0 as the slice start instead of the index.

The suffix array is built by sorting indices from 0 to len(s). The key function takes an index i and returns the suffix s[i:] for sorting.

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