Each rank summarizes one half. Ranks of two adjacent known-length halves summarize a doubled prefix.

A suffix is identified by where it begins. Once length-L prefixes have ranks, a length-2L prefix is exactly the pair of ranks for its two halves.

What the function promises: Return starting positions of all suffixes in lexicographic order.

def suffix_array(text):
    n = len(text)
    order = list(range(n))
    rank = [ord(char) for char in text]
    width = 1
    while width < n:
        order.sort(key=lambda i: (rank[i], rank[i+width] if i+width < n else -1))
        new_rank = [0] * n
        for j in range(1, n):
            before, current = order[j-1], order[j]
            old_pair = (rank[before], rank[before+width] if before+width < n else -1)
            new_pair = (rank[current], rank[current+width] if current+width < n else -1)
            new_rank[current] = new_rank[before] + (new_pair != old_pair)
        rank = new_rank
        width *= 2
    return order

assert suffix_array("banana") == [5,3,1,0,4,2]
assert suffix_array("") == []

Work and storage: O(n log² n) time here because each doubling round comparison-sorts, with O(n) working space.

When to recognize it: Ranks of two adjacent known-length halves summarize a doubled prefix.

Check before applying it: This teaching implementation sorts tuples each round and is not the most advanced linear-time construction.

Binary-search the suffix array for the pattern’s lower and upper lexicographic boundaries.