Induced Sorting
Induced Sorting Induced sorting is a technique used to construct suffix arrays in linear time. Instead of sorting all suffixes directly, it sorts a subset of suffixes and then induces the order of the remaining ones. This idea forms the foundation of modern linear-time suffix array algorithms such as SA-IS. Problem Given a string $S$ of length $n$, construct the suffix array: $$ SA = \text{sorted indices of all suffixes...