Reduction ratio of the IS-algorithm: worst and random cases

Vincent Jugé

We study the IS-algorithm, a well-known linear-time algorithm for computing the suffix array of a word. This algorithm relies on transforming the input word $w$ into another word,…