On the maximum number of distinct factors of a binary string |
| |
Authors: | Jeffrey Shallit |
| |
Affiliation: | 1. Department of Computer Science, University of Waterloo, Waterloo, N2L 3G1, Ontario, Canada
|
| |
Abstract: | In this note we prove that a binary string of lengthn can have no more than (2^{k + 1} - 1 + left( {mathop {n - k + 1}limits_2 } right)) distinct factors, wherek is the unique integer such that 2k + k - 1 ≤ n < 2k+1 + k. Furthermore, we show that for eachn, this bound is actually achieved. The proof uses properties of the de Bruijn graph. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|