Suffix trees concept in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a suffix tree?

A suffix tree is a special tree structure that shows all the suffixes of a given string. It helps find patterns quickly in the string.

beginner

Why are suffix trees useful?

Suffix trees let us search for any substring in a string very fast, often in time proportional to the substring length, not the whole string.

beginner

What does each path from the root to a leaf in a suffix tree represent?

Each path from the root to a leaf represents a suffix of the original string.

intermediate

How does a suffix tree differ from a suffix array?

A suffix tree is a tree structure showing suffixes explicitly, while a suffix array is a sorted list of suffix positions. Trees use more memory but allow faster queries.

intermediate

What is the typical time complexity to build a suffix tree for a string of length n?

A suffix tree can be built in linear time, which means roughly proportional to the length n of the string.

What does a suffix tree represent for a string?

A Only the longest suffix

B All prefixes of the string

C All substrings of the string

D All suffixes of the string

A suffix tree explicitly represents all suffixes of a string as paths from the root to leaves.

Which of these is a key advantage of suffix trees?

A Fast substring search

B Uses very little memory

C Easy to build manually

D Only works for numbers

Suffix trees allow fast substring searches, often in time proportional to the substring length.

What is the shape of a suffix tree?

A A graph with cycles

B A flat list of suffixes

C A tree with edges labeled by substrings

D A single string

Suffix trees are trees where edges are labeled by substrings, representing suffixes.

How long does it usually take to build a suffix tree for a string of length n?

A Quadratic time (proportional to n²)

B Linear time (proportional to n)

C Exponential time

D Constant time

Suffix trees can be built in linear time, meaning the time grows roughly in proportion to the string length.

Which data structure uses less memory but slower substring queries compared to suffix trees?

A Suffix array

B Binary search tree

C Hash table

D Linked list

Suffix arrays use less memory but substring queries are slower compared to suffix trees.

Explain what a suffix tree is and how it helps in searching substrings.

Think about how suffixes of a string are organized in a tree.

Describe the difference between a suffix tree and a suffix array.

One is a tree, the other is a sorted list.