A border of a string is a non-empty prefix of the string that is also a suffix of the string, and a string is unbordered if it has no border. Loptev, Kucherov, and Starikovskaya [CPM 2015] conjectured the following: If we pick a string of length n from a fixed alphabet uniformly at random, then the expected length of the maximal unbordered factor is n - O(1). We prove that this conjecture is true by proving that the expected value is in fact n - Θ(σ~(-1)), where σ is the size of the alphabet. We discuss some of the consequences of this theorem.
展开▼
