Give the prefix doubling construction of a suffix array, state its complexity with a comparison sort and with a radix sort at each round, and say what the LCP array adds and how it is built in linear time.

Give the prefix doubling construction of a suffix array, state its complexity with a comparison sort and with a radix sort at each round, and say what the LCP array adds and how it is built in linear time.

Approach: Sort the suffixes by their first 2^k characters using the ranks from the previous round as a pair of keys, then count the rounds and the cost of each.

O(n log^2 n) with a comparison sort and O(n log n) with a radix sort. Each round assigns every suffix a rank from its first 2^k characters, and the rank of a suffix by its first 2^{k+1} characters is determined by the pair of ranks (rank[i], rank[i + 2^k]) from the previous round, so one sort of n pairs advances the prefix length from 2^k to 2^{k+1}. After log n rounds the prefix covers the whole string and the order is final. Sorting the rank pairs by comparison costs O(n log n) per round for O(n log^2 n) overall, while a two-pass radix sort on the pair costs O(n) per round and gives O(n log n). SA-IS reaches O(n) by an induced sorting argument. The LCP array stores the longest common prefix of adjacent entries of the suffix array, which turns substring queries into range minimum queries, and Kasai's algorithm builds it in O(n) by walking the suffixes in text order and using the fact that dropping the first character shortens the previous LCP by at most one.

Follow-up: How do the suffix array and the LCP array together count the distinct substrings of a string?

Key concepts: prefix doubling, rank pairs, radix sort, lcp array.