TY - GEN
T1 - Computing the Longest Unbordered Substring
AU - Gawrychowski, Pawel
AU - Kucherov, Gregory
AU - Sach, Benjamin G
AU - Starikovskaya, Tatiana
N1 - Date of Acceptance: 21/01/2015
PY - 2015/9/5
Y1 - 2015/9/5
N2 - A substring of a string is unbordered
if its only border is the empty string. The study of unbordered
substrings goes back to the paper of Ehrenfeucht and Silberger [Discr.
Math 26 (1979)]. The main focus of their and subsequent papers was to
elucidate the relationship between the longest unbordered substring and
the minimal period of strings. In this paper, we consider the
algorithmic problem of computing the longest unbordered substring of a
string. The problem was introduced recently by G. Kucherov et al. [CPM
(2015)], where the authors showed that the average-case running time of
the simple, border-array based algorithm can be bounded by O(max{n,n2/σ4}) for σ being the size of the alphabet. (The worst-case running time remained O(n2).) Here we propose two algorithms, both presenting substantial theoretical improvements to the result of [11]. The first algorithm has O(nlogn) average-case running time and O(n2) worst-case running time, and the second algorithm has O(n1.5) worst-case running time.
AB - A substring of a string is unbordered
if its only border is the empty string. The study of unbordered
substrings goes back to the paper of Ehrenfeucht and Silberger [Discr.
Math 26 (1979)]. The main focus of their and subsequent papers was to
elucidate the relationship between the longest unbordered substring and
the minimal period of strings. In this paper, we consider the
algorithmic problem of computing the longest unbordered substring of a
string. The problem was introduced recently by G. Kucherov et al. [CPM
(2015)], where the authors showed that the average-case running time of
the simple, border-array based algorithm can be bounded by O(max{n,n2/σ4}) for σ being the size of the alphabet. (The worst-case running time remained O(n2).) Here we propose two algorithms, both presenting substantial theoretical improvements to the result of [11]. The first algorithm has O(nlogn) average-case running time and O(n2) worst-case running time, and the second algorithm has O(n1.5) worst-case running time.
U2 - 10.1007/978-3-319-23826-5_24
DO - 10.1007/978-3-319-23826-5_24
M3 - Conference Contribution (Conference Proceeding)
SN - 9783319238258
T3 - Lecture Notes in Computer Science
SP - 246
EP - 257
BT - String Processing and Information Retrieval
PB - Springer International Publishing AG
T2 - International Symposium on String Processing and Information Retrieval
Y2 - 1 September 2015
ER -