Algorithms / Suffix Ordering
Least You Need to Know: Suffix Ordering, Lexicographic Structure, and LCP Intuition
Suffix-based reasoning sorts all suffixes of a string lexicographically. Even without implementing a full suffix array from scratch, it helps to know how lexicographic suffix order exposes repeated-substring structure and longest-common-prefix reasoning.
The least you need to know
- A suffix is a substring that starts at some position and runs to the end.
- Sorting suffixes lexicographically defines suffix-array order.
- Adjacent suffixes in sorted order are where repeated prefixes show up most locally.
- LCP means longest common prefix.
- Suffix ordering is useful for repeated-substring and pattern-location reasoning.
Key notation
suffix i
substring `s[i:]`
SA
suffix array: starting indices in sorted suffix order
LCP
longest common prefix of two suffixes
Tiny worked example
- For string `banana`, suffixes include `banana`, `anana`, `nana`, `ana`, `na`, `a`.
- Sorting them lexicographically places similar prefixes near each other, such as `a`, `ana`, `anana`.
- The longest repeated substring can then be found by checking large LCP values among adjacent sorted suffixes.
- This is the high-level reason suffix arrays are powerful.
Common mistakes
- Students sometimes compare whole suffix sets conceptually but forget that a suffix must run to the end of the string.
- The longest repeated substring is captured by adjacent suffixes in sorted order, not arbitrary distant pairs.
- Suffix-array order is lexicographic on suffix strings, not on original indices.
How to recognize this kind of problem
- You care about repeated substrings or lexicographic order of all suffixes.
- Longest common prefix between nearby suffixes is relevant.
- The problem wants a global view of substring repetition structure.