AlgoScope

Suffix Array

The starting indices of all suffixes, sorted. Binary search finds substrings.

Data structures, data structure, advanced
Row 2: anana.startsuffix0123455a3ana1anana0banana4na2nana
Row 2: anana.startsuffix0123455a3ana1anana0banana4na2nana

Suffix Array: Binary search for a pattern

Decision, step 2 of 5

Rows 0 to 5 are still possible. The middle row 2 holds "anana" (start 1). "nan" sorts after it, so the block can only be below: search rows 3 to 5.

How suffix array works

Cost

Build
O(n log n)
Substring query
O(m log n)
Space
O(n)

Leads to

Topics that need this one first.

Taught by the same lesson

Suffix Array covers these too, in the same run.