Maximal repetitions in strings
Maximal repetitions in strings
复制标题
字符串中的最大重复次数
DOI：
10.1016/j.jcss.2007.09.003
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Lucian Ilie
中科院分区：
文献类型：
--
作者：
M. Crochemore;Lucian Ilie
任何算法在O（n）时间内计算长度为n的字符串中的所有重复的基石是最大重复（运行）的数量是线性的。因此，分析此类算法的运行时间的最重要部分是计算运行次数。Kolpakov和Kucherov [R.科尔帕科夫湾Kucherov，在线性时间中寻找单词中的最大重复，在：Proc. of FOCS'99，IEEE Computer Society Press，1999，pp. 596-604]证明它是CN，但不能提供C的任何值。最近，Rytter [W. Rytter，The number of runs in a string：Improved analysis of the linear upper bound，在：B。Durand，W.托马斯（编辑），2006年，《中国科学院学报》（卷106），第106期。科学，第3884卷，施普林格，柏林，海德堡，2006年，第3884页。184-195]证明了c 5。Puglisi等人改进了他的分析，得到3.48，Rytter改进了他的分析，得到3.44（两者都提交了）。科尔帕科夫和库切罗夫的猜想得到了计算的支持，即c=1。在这里，我们通过证明c = 1.6来显着改进以前的结果，并展示如何通过计算机验证将其改进到1.18或更小。虽然猜想可能很难证明，但我们相信我们的工作为所有实际目的提供了一个很好的近似。对于指数和线性性的更强结果，我们给出了第一个显式界：5.6n。Kolpakov和Kucherov没有任何和Rytter认为“不满意”的界限，可以推断出他的证明。我们的界限也可以通过计算机验证提高到2.9n或更小。
The cornerstone of any algorithm computing all repetitions in strings of length n in O(n) time is the fact that the number of maximal repetitions (runs) is linear. Therefore, the most important part of the analysis of the running time of such algorithms is counting the number of runs. Kolpakov and Kucherov [R. Kolpakov, G. Kucherov, Finding maximal repetitions in a word in linear time, in: Proc. of FOCS'99, IEEE Computer Society Press, 1999, pp. 596–604] proved it to be cn but could not provide any value for c. Recently, Rytter [W. Rytter, The number of runs in a string: Improved analysis of the linear upper bound, in: B. Durand, W. Thomas (Eds.), Proc. of STACS'06, in: Lecture Notes in Comput. Sci., vol. 3884, Springer, Berlin, Heidelberg, 2006, pp. 184–195] proved that c⩽5. His analysis has been improved by Puglisi et al. to obtain 3.48 and by Rytter to 3.44 (both submitted). The conjecture of Kolpakov and Kucherov, supported by computations, is that c=1. Here we improve dramatically the previous results by proving that c⩽1.6 and show how it could be improved by computer verification down to 1.18 or less. While the conjecture may be very difficult to prove, we believe that our work provides a good approximation for all practical purposes. For the stronger result concerning the linearity of the sum of exponents, we give the first explicit bound: 5.6n. Kolpakov and Kucherov did not have any and Rytter considered “unsatisfactory” the bound that could be deduced from his proof. Our bound could be as well improved by computer verification down to 2.9n or less.