Computing Maximum Number of Runs in Strings
Computing Maximum Number of Runs in Strings
复制标题
计算字符串中的最大游程数
DOI：
10.1007/978-3-642-34109-0_33
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Kazuhiko Kusano
中科院分区：
文献类型：
--
作者：
Yagi T;Ito D;Okada Y;Akamatsu W;Nihei Y;Yoshizaki T;Yamanaka S;Okano H;Suzuki N;Kazuhiko Kusano
单词中的一次重复(也称为最大重复)是不可扩展的重复。在一个长度的字符串中寻找最大游程数ρ(N)是一个具有挑战性的问题。虽然已知ρ(N) ≤ 1.029n，且存在大的ρ(N) ≥ 0.945n，但ρ(N)的精确值仍然未知。已经提出了几种算法来有效地计算字符串中的游程，并且这些算法可以得到较小的ρ(N)。在本文中，我们专注于计算给定长度参数n的ρ(N)，而不是穷举地计算每个长度n的串的所有游程。我们报告了ρ(N)对于≤ 66的二进制字符串的精确值，以及包含ρ(N)游程的字符串。
A run (also called maximal repetition) in a word is a non-extendable repetition. Finding the maximum numberρ(n) of runs in a string of lengthnis a challenging problem. Although it is known thatρ(n) ≤ 1.029nfor anynand there exists largensuch thatρ(n) ≥ 0.945n, the exact value ofρ(n) is still unknown. Several algorithms have been proposed to count runs in a string efficiently, andρ(n) can be obtained for smallnby these algorithms. In this paper, we focus on computingρ(n) for given length parametern, instead of exhaustively counting all runs for every string of lengthn. We report exact values ofρ(n) for binary strings forn≤ 66, together with the strings which containρ(n) runs.