On Maximal Unbordered Factors

Abstract

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 $\sigma \ge 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.

Accepted to the 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015)

References in corpus (1)

• Internal Pattern Matching Queries in a Text and Applications