A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS-Algorithm

Cyril Nicaud (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

We show that there are asymptotically γn LMS-factors in a random word of length n, for some explicit γ that depends on the model of randomness under consideration. Our results hold for uniform distributions, memoryless sources and Markovian sources. From this analysis, we give new insight on the typical behavior of the IS-algorithm [9], which is one of the most efficient algorithms available for computing the suffix array.

Domaines: Algorithme et structure de données [cs.DS]

Cyril Nicaud. A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS-Algorithm. CPM 2015, Jun 2015, Ischia Island, Italy. pp.374-384, ⟨10.1007/978-3-319-19929-0_32⟩. ⟨hal-01719172⟩