Suffix arrays in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a suffix array?

A suffix array is a sorted array of all suffixes of a string. It stores the starting positions of these suffixes in sorted order.

beginner

Why are suffix arrays useful?

Suffix arrays help quickly find patterns or substrings in a text. They are used in text search, data compression, and bioinformatics.

intermediate

How does a suffix array differ from a suffix tree?

A suffix array is a simple list of suffix positions sorted lexicographically, while a suffix tree is a tree structure representing all suffixes. Suffix arrays use less memory but may be slower for some queries.

intermediate

What is the time complexity to build a suffix array using efficient algorithms?

Efficient algorithms can build a suffix array in O(n) or O(n log n) time, where n is the length of the string.

intermediate

How can suffix arrays help in finding the longest repeated substring?

By examining the longest common prefix (LCP) between adjacent suffixes in the suffix array, we can find the longest repeated substring in the text.

What does each element in a suffix array represent?

A The frequency of a character

B The length of a suffix

C The position of a prefix

D The starting index of a suffix in the original string

Each element in a suffix array is the starting index of a suffix in the original string.

What is the main advantage of suffix arrays over suffix trees?

A They are easier to build

B They use less memory

C They store prefixes instead of suffixes

D They are slower for all queries

Suffix arrays use less memory compared to suffix trees, making them more space-efficient.

Which of the following is a common use of suffix arrays?

A Encrypting data

B Sorting numbers

C Finding substrings quickly

D Calculating factorials

Suffix arrays are commonly used to find substrings quickly in a text.

What does LCP stand for in the context of suffix arrays?

A Longest Common Prefix

B Least Common Position

C Longest Character Pattern

D Last Character Pointer

LCP stands for Longest Common Prefix, which helps find repeated substrings.

If a string has length n, what is the maximum number of suffixes it has?

A n

B n-1

C 2n

D n squared

A string of length n has exactly n suffixes, one starting at each position.

Explain what a suffix array is and how it is constructed from a string.

Think about listing all endings of a word and sorting them alphabetically.

Describe one practical application of suffix arrays and how they help solve the problem.

Consider how you might quickly find if a word appears inside a large text.