TY - GEN

T1 - On Maximal Unbordered Factors

AU - Kucherov, Gregory

AU - Loptev, Alexander

AU - Starikovskaya, Tatiana

PY - 2015/6/16

Y1 - 2015/6/16

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-19929-0_29

DO - 10.1007/978-3-319-19929-0_29

M3 - Conference Contribution (Conference Proceeding)

SN - 9783319199283

T3 - Lecture Notes in Computer Science

SP - 343

EP - 354

BT - Combinatorial Pattern Matching

PB - Springer International Publishing AG

ER -