论文标题
IS-Algorithm的降低比：最坏和随机情况
Reduction ratio of the IS-algorithm: worst and random cases
论文作者
论文摘要
我们研究IS-Algorithm，这是一种用于计算单词后缀阵列的众所周知的线性时间算法。该算法依赖于将输入单词$ w $转换为另一个单词，称为$ w $的简化单词，至少短两次；然后，该算法递归计算简化单词的后缀阵列。在本文中，我们研究了IS-Algorithm的降低比，即输入单词的长度与减少输入单词$ k $ times后获得的单词之间的比率。我们研究了两个最坏的情况，在这些情况下，我们发现了精确的结果和随机情况，在这些情况下，我们证明了一些强烈的收敛现象。最后，我们证明，如果输入单词是一个随机选择的$ n $的单词，我们的期望不应超过$ \ log（\ log（n））$递归函数调用。
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, called the reduced word of $w$, that will be at least twice shorter; then, the algorithm recursively computes the suffix array of the reduced word. In this article, we study the reduction ratio of the IS-algorithm, i.e., the ratio between the lengths of the input word and the word obtained after reducing $k$ times the input word. We investigate both worst cases, in which we find precise results, and random cases, where we prove some strong convergence phenomena. Finally, we prove that, if the input word is a randomly chosen word of length $n$, we should not expect much more than $\log(\log(n))$ recursive function calls.
