📜 WAYPOINT LESSON

Suffix Arrays and LCP

⭐⭐⭐ advanced⏳ 30 min read📍 Lesson 167 of 281

Sort suffixes by doubling rank pairs, then Kasai's walk gives every adjacent LCP in O(n) — distinct substrings = n(n+1)/2 minus the LCP sum.

Order, then count

Suffix-array construction by rank doubling is O(n log^2 n) with a plain sort — fast enough for n = 2000 course loads. Kasai's algorithm walks the text left-to-right, each step's LCP dropping at most one: O(n) total. The counting identity n(n+1)/2 - Σ LCP falls out of how sorted suffixes share prefixes.

⚡ Now practice

Ready to Code

String TrioHash-based per-length distinct counting, Z-array construction at 100k, and Z-based pattern matching with overlaps.

3 challenges · · ~110 min