Maximal Unbordered Factors of Random Strings

Abstract

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 other than itself. Loptev, Kucherov, and Starikovskaya [CPM 2015] conjectured the following: If we pick a string of length $n$ from a fixed non-unary alphabet uniformly at random, then the expected maximum length of its unbordered factors is $n-O(1)$. We confirm this conjecture by proving that the expected value is, in fact, $n-\Theta ({\sigma }^{-1})$, where $\sigma$ is the size of the alphabet. This immediately implies that we can find such a maximal unbordered factor in linear time on average. However, we go further and show that the optimum average-case running time is in $\Omega (\sqrt{n})\cap O(\sqrt{n{\log }_{\sigma }n})$ due to analogous bounds by Czumaj and Gąsieniec [CPM 2000] for the problem of computing the shortest period of a uniformly random string.

A preliminary version with weaker results was presented at the 23rd Symposium on String Processing and Information Retrieval (SPIRE '16)