THE "RUNS" THEOREM
THE "RUNS" THEOREM
复制标题
DOI：
10.1137/15m1011032
复制
发表时间：
2017-01-01
影响因子：
1.6
通讯作者：
Tsuruta, Kazuya
中科院分区：
文献类型：
--
作者：
Bannai, Hideo;Tomohiro, I;Tsuruta, Kazuya
我们为基于林登单词的字符串中的最大重复（或运行）提供了新的表征。表征导致了所谓的“运行”猜想的证明[R. M. Kolpakov和G. Kucherov，IEEE计算机科学基础（FOCS），IEEE计算机社会，加利福尼亚州Los Alamitos，1999年，第596-604页的IEEE Computer Society（focs）论文集），该论文指出，Rho的最大运行数量最大。 （n）长度为n小于n。考虑到过去15年来解决这个问题的众多努力，证明非常简单，并显着提高了我们对弦乐中如何发生跑步的理解。此外，我们获得了3N的上限，对于长度为n的指数sigma（n）的最大指数总和，在Crochemore等人的4.1N结合上改进了。 [J。离散算法，14（2012），第29-36页，以及相关问题的其他改进范围。该表征还产生了一种新的，概念上简单的线性时间算法，用于计算字符串中的所有运行。我们算法的一个显着特征是，与所有现有的线性时间算法不同，它不利用字符串的lempel-ziv分解。我们还建立了Lyndon树的运行与节点之间的关系，该关系为Kociumaka等人最近解决的2个周期查询问题提供了一个简单的最佳解决方案。
We give a new characterization of maximal repetitions (or runs) in strings based on Lyndon words. The characterization leads to a proof of what was known as the "runs" conjecture [R. M. Kolpakov and G. Kucherov, Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 1999, pp. 596-604]), which states that the maximum number of runs rho(n) in a string of length n is less than n. The proof is remarkably simple, considering the numerous endeavors to tackle this problem in the last 15 years, and significantly improves our understanding of how runs can occur in strings. In addition, we obtain an upper bound of 3n for the maximum sum of exponents sigma(n) of runs in a string of length n, improving on the best known bound of 4.1n by Crochemore et al. [J. Discrete Algorithms, 14 (2012), pp. 29-36], as well as other improved bounds on related problems. The characterization also gives rise to a new, conceptually simple linear-time algorithm for computing all the runs in a string. A notable characteristic of our algorithm is that, unlike all existing linear-time algorithms, it does not utilize the Lempel-Ziv factorization of the string. We also establish a relationship between runs and nodes of the Lyndon tree, which gives a simple optimal solution to the 2-period query problem that was recently solved by Kociumaka et al.