Given a string S of length n, its maximal unbordered factor is the longest factor which does not have a border. In this work we investigate the relationship between n and the length of the maximal unbordered factor of S. We prove that for the alphabet of size σ≥5 the expected length of the maximal unbordered factor of a string of length n is at least 0.99n (for sufficiently large values of n). As an application of this result, we propose a new algorithm for computing the maximal unbordered factor of a string.
|Title of host publication||Combinatorial Pattern Matching|
|Subtitle of host publication||26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings|
|Publisher||Springer International Publishing AG|
|Number of pages||12|
|Publication status||Published - 16 Jun 2015|
|Name||Lecture Notes in Computer Science|
|Publisher||Springer International Publishing|