Algorithms to Compute the Lyndon Array
Algorithms to Compute the Lyndon Array
复制标题
计算 Lyndon 数组的算法
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
W. F. Smyth
中科院分区：
文献类型：
--
作者：
F. Franek;A. S. M. S. Islam;Mohammad Sohel Rahman;W. F. Smyth
我们首先描述了用于计算文献中建议的林登阵列的三种算法，但没有给出结构化的博览会。这些算法中的两种在最坏的情况下在二次时间内执行，第三个实现线性时间，但以牺牲后缀阵列和x的逆后缀阵列为代价。然后，我们继续描述一种新算法的两个变体，该变体避免了先前计算全局数据结构并在最差的n log n时间内执行。实验证据表明，除了这五种算法中，所有算法中的所有算法都仅在实践中仅需要线性执行时间，而两种新算法的速度更快。我们猜想存在一种快速且最差的线性时间算法来计算也是基本的Lyndon阵列（不使用诸如后缀阵列之类的全局数据结构）。
We first describe three algorithms for computing the Lyndon array that have been suggested in the literature, but for which no structured exposition has been given. Two of these algorithms execute in quadratic time in the worst case, the third achieves linear time, but at the expense of prior computation of both the suffix array and the inverse suffix array of x. We then go on to describe two variants of a new algorithm that avoids prior computation of global data structures and executes in worst-case n log n time. Experimental evidence suggests that all but one of these five algorithms require only linear execution time in practice, with the two new algorithms faster by a small factor. We conjecture that there exists a fast and worst-case linear-time algorithm to compute the Lyndon array that is also elementary (making no use of global data structures such as the suffix array).