Linear Time Runs over General Ordered Alphabets
Linear Time Runs over General Ordered Alphabets
复制标题
线性时间运行于一般有序字母表上
DOI：
10.4230/lipics.icalp.2021.63
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
J. Fischer
中科院分区：
文献类型：
--
作者：
J. Ellert;J. Fischer
在字符串中运行是最大的周期性基因。例如，字符串$ \ texttt {bananatree} $包含运行$ \ texttt {anana} =（\ texttt {an}）^{3/2} $和$ \ texttt {ee} 2 $。在任何长度-N $字符串中都有不到$ n $运行，并且在线性可吻合的字母上计算所有运行的字符串运行$ \ MATHCAL {O}（N）$ TIME（Bannai等，Soda等，2015， ）。 Kosolobov猜想，也存在一般有序字母的线性时间运行算法（Inf。Process。Lett。2016）。 Crochemore等人几乎证明了这一猜想，他提出了$ \ Mathcal {o}（n \ alpha（n））$ time Algorithm（其中$ \ alpha（n）$是一个非常缓慢增长的逆逆转录ackermann功能）。我们通过利用Lyndon数组的组合属性来展示如何实现$ \ MATHCAL {O}（N）$时间，从而证明了Kosolobov的猜想。
A run in a string is a maximal periodic substring. For example, the string $\texttt{bananatree}$ contains the runs $\texttt{anana} = (\texttt{an})^{3/2}$ and $\texttt{ee} = \texttt{e}^2$. There are less than $n$ runs in any length-$n$ string, and computing all runs for a string over a linearly-sortable alphabet takes $\mathcal{O}(n)$ time (Bannai et al., SODA 2015). Kosolobov conjectured that there also exists a linear time runs algorithm for general ordered alphabets (Inf. Process. Lett. 2016). The conjecture was almost proven by Crochemore et al., who presented an $\mathcal{O}(n\alpha(n))$ time algorithm (where $\alpha(n)$ is the extremely slowly growing inverse Ackermann function). We show how to achieve $\mathcal{O}(n)$ time by exploiting combinatorial properties of the Lyndon array, thus proving Kosolobov's conjecture.