Suffix Array
The starting indices of all suffixes, sorted. Binary search finds substrings.
Suffix Array: Binary search for a pattern
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.
Cost
- Build
- O(n log n)
- Substring query
- O(m log n)
- Space
- O(n)
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Suffix Array covers these too, in the same run.