Intuition The ONE core ideaA string can be cut into all its tails (suffixes), and if you put those tails in dictionary order you unlock fast substring search, repeat-finding, and counting. Everything on the parent page is just two things: how to sort those tails quickly (the suffix array) and how much neighboring tails overlap (the LCP array).
This page builds every symbol the parent note uses, starting from "what is a string" and never using a piece of notation before it is drawn and explained. If a symbol below already feels obvious, skim it — but each later idea leans on the earlier ones, so the order matters.
Definition String, length, and characterA string s length as n square-bracket index : s [ i ] i count from 0 (0-indexed), so the first character is s [ 0 ] s [ n − 1 ]
Picture a row of numbered boxes. Box number 0 holds the first letter.
Intuition Why 0-indexing ands [ i ] S A [ r ] s [ i + h ] r k [ i + k ]
Why the topic needs it: the suffix array is a list of positions, so "position" must be rock solid.
suf ( i ) suffix starting at i is the piece of the string from position i suf ( i ) = s [ i .. n − 1 ] ..
If s = banana suf ( 0 ) = banana suf ( 3 ) = ana suf ( 5 ) = a n
Intuition Why cut into suffixes at all?Here is the trick the whole chapter rests on: any substring is the beginning (prefix) of some suffix. Want to search for "ana" inside the word? "ana" starts suf ( 1 ) suf ( 3 )
Why the topic needs it: the suffix array sorts these objects.
Definition Prefix and longest common prefix (LCP)A prefix of a string is a chunk taken from the front : the first few characters.
The longest common prefix of two strings is how many characters they share from the start before they first differ .
Line the two strings up left-aligned and read across until the first mismatch. The number of matching columns is the LCP length.
Worked example LCP by eyeanana ana a , n , a anana n ana 3
Why the topic needs it: the entire LCP array (Section 3 of the parent) is just this number computed for neighboring sorted suffixes.
Definition Lexicographic order (< s [ 0 ] runs out first while matching, the shorter one is smaller (it comes first).
We reuse the ordinary alphabet order for single characters: a < b < c < … a , b , n a < b < n
Common mistake "Longer strings are bigger."Why it feels right: more letters, more value. Truth: length is irrelevant until you hit a mismatch. If everything matches and one ends, that shorter one is smaller — exactly like car comes before card in a dictionary. This "ran-out = smallest" rule is why the parent uses a − 1
Why the topic needs it: "sorted lexicographically" is the definition of the suffix array.
Intuition The end-of-string is thesmallest thing
When a suffix ends, imagine an invisible "nothing" character that beats every real letter (it is smaller than a − 1 r k [ i + k ] i + k ≥ n
S A r n suffix array stores their starting positions in that sorted order.
We use r r = 0 , 1 , … , n − 1 S A [ r ] = the starting index of the r -th smallest suffix.
Read it as: "go to shelf number r
Why the topic needs it: S A is the output of construction. Everything downstream (binary search, LCP) reads it.
S A S A 0 , 1 , … , n − 1
rank [ i ] S A r rank array answers the reverse question: "starting position i rank [ S A [ r ]] = r inverse permutations : apply one then the other and you land back where you started.
If S A = [ 5 , 3 , 1 , 0 , 4 , 2 ] 5 0 3 1 rank = [ 3 , 2 , 5 , 1 , 4 , 0 ] 0 3
both directions
To sort we naturally produce S A i = 0 , 1 , 2 , … rank
Why the topic needs it: the predecessor lookup j = S A [ rank [ i ] − 1 ]
k k r k [ i ] rank of suffix i k (ties allowed — equal first-k
Start with k = 1 k = 2 k = 4 k = 8 doubling each round until k ≥ n k
Intuition Why doubling, and why apair ?
The first 2 k i k i k i + k 2 k pair ( r k [ i ] , r k [ i + k ])
Why the topic needs it: this is the O ( n log n ) log n
O ( f ( n )) O ( f ( n )) n O ( n ) O ( n log n ) log n
log n log 2 n n double starting from 1 before you reach n n = 8 3 1 → 2 → 4 → 8
Why the topic needs it: the number of doubling rounds is exactly ⌈ log 2 n ⌉ O ( n log n )
h h i carry h to the next position, only shrinking it by 1, because of the "LCP drops by at most 1" lemma (parent Section 3).
Why the topic needs it: h O ( n ) O ( n 2 ) h
Characters s at i (0-indexed)
Character order a lt b lt n
Lexicographic order of strings
Self-test: can you answer each before revealing?
What does s [ i ] The character at position i 0 s [ 0 ] s [ n − 1 ]
What is suf ( i ) The tail of s i s [ i .. n − 1 ] n
Why does every substring relate to suffixes? Every substring is a prefix (front chunk) of some suffix, so studying suffixes covers all substrings.
How do you compare two strings lexicographically? Compare character by character from the left; the first mismatch decides; if one runs out while matching, the shorter one is smaller.
What is S A [ r ] The starting index of the r
How are S A rank They are inverse permutations: rank [ S A [ r ]] = r S A rank
What is r k [ i ] Rank of suffix i k 2 k ( r k [ i ] , r k [ i + k ])
Why is − 1 i + k ≥ n A suffix that ran off the end acts like an empty/smallest character, so it must sort before any real character — encoded as − 1
What does O ( n log n ) About log 2 n O ( n )
What does h Carries the current overlap length across positions, shrinking by at most 1 per step, giving linear-time LCP.
