Suffix arrays in Data Structures Theory - Mini Project: Build & Apply

Building a Simple Suffix Array

📖 Scenario: Imagine you have a word and you want to organize all its endings (suffixes) in alphabetical order. This helps in searching and analyzing text efficiently.

🎯 Goal: You will build a simple suffix array for a given word. A suffix array is a list of all suffixes of the word sorted alphabetically, represented by their starting positions.

📋 What You'll Learn

Create a list of all suffixes of the word with their starting indexes

Create a helper variable to hold the length of the word

Sort the suffixes alphabetically using their text

Create the final suffix array as a list of starting indexes of sorted suffixes

💡 Why This Matters

🌍 Real World

Suffix arrays are used in text search engines, DNA sequence analysis, and data compression to quickly find patterns in large texts.

💼 Career

Understanding suffix arrays is useful for software engineers working in search technologies, bioinformatics, and data processing.

1

Create the list of suffixes

Create a variable called word and set it to the string "banana". Then create a list called suffixes that contains tuples of the form (index, suffix_text) for every suffix of word. The index is the starting position of the suffix in word, and suffix_text is the substring from that index to the end.

Data Structures Theory

word = "banana"
# Your code here

Need a hint?

Use a list comprehension with range(len(word)) to get all suffixes.

2

Create a helper variable for word length

Create a variable called n and set it to the length of word using the len() function.

Data Structures Theory

word = "banana"
suffixes = [(i, word[i:]) for i in range(len(word))]
n = len(word)
# Your code here

Need a hint?

Use len(word) to get the length.

3

Sort the suffixes alphabetically

Sort the list suffixes alphabetically by the suffix text (the second item in each tuple) using the sort() method with a key argument.

Data Structures Theory

word = "banana"
suffixes = [(i, word[i:]) for i in range(len(word))]
n = len(word)
suffixes.sort(key=lambda x: x[1])
# Your code here

Need a hint?

Use suffixes.sort(key=lambda x: x[1]) to sort by suffix text.

4

Create the suffix array of starting indexes

Create a list called suffix_array that contains only the starting indexes from the sorted suffixes list.

Data Structures Theory

word = "banana"
suffixes = [(i, word[i:]) for i in range(len(word))]
n = len(word)
suffixes.sort(key=lambda x: x[1])
suffix_array = [i for i, s in suffixes]
# Your code here

Need a hint?

Use a list comprehension to extract the first item of each tuple in suffixes.