Maximal Unbordered Factors of Random Strings

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 - \varTheta (\sigma ^{-1})\), where \(\sigma \) is the size of the alphabet. We discuss some of the consequences of this theorem.