A -step approach to the maximum number of distinct squares and runs in strings

详细信息    查看全文

• 作者：Antoine Deza ; Frantisek Franek
• 关键词：Strings ; Runs ; Distinct squares ; (d ; n)(d ; n)-parameterization ; dd-step approach
• 刊名：Discrete Applied Mathematics
• 出版年：30 January, 2014
• 年：2014
• 卷：163
• 期：part_P3
• 页码：268-274
• 全文大小：398 K

文摘

Fraenkel and Simpson conjectured in 1998 that the number of distinct squares in a string is at most its length. Kolpakov and Kucherov conjectured in 1999 that the number of runs in a string is also at most its length. Since then, both conjectures attracted the attention of many researchers and many results have been presented, including asymptotic lower bounds for both, asymptotic upper bounds for runs, and universal upper bounds for distinct squares in terms of the length. In this survey we point to the combined role played by the length and the number of distinct symbols of the string in both problems. Let us denote , respectively , the maximum number of distinct primitively rooted squares, respectively runs, over all strings of length containing exactly distinct symbols. We study both functions and and revisit earlier results and conjectures with the -parameterized approach. The parameterized approach reveals regularities for both and which have been computationally verified for all known values. In addition, the approach provides a computationally efficient framework. We were able to determine all previously known values for in a matter of hours, confirming the results reported by Kolpakov and Kucherov, and were able to extend the computations up to . Similarly, we were able to extend the computations up to for . We point out that ; that is, among all strings of length 33, no binary string achieves the maximum number of distinct primitively rooted squares, and that for . The computations also reveal the existence of unexpected binary run-maximal string of length containing a quadruple of identical symbols .