Suffix Array
The starting indices of all suffixes, sorted; binary search finds substrings.
Decision · step 2 of 5Suffix 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.
What you will see
Suffixes listed and sorted; a binary search narrows the range that starts with the pattern.
Cost
| build | O(n log n) |
|---|---|
| substring query | O(m log n) |
| Space | O(n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.