Rank Among the Suffixes — Solution & Editorial

Back to the Problem

Build the suffix array; its inverse permutation gives each suffix's rank in O(1) per query.

Complexity: O(|S| log |S| + Q)