Computing the Longest Unbordered Substring

Pawel Gawrychowski, Gregory Kucherov, Benjamin G Sach, Tatiana Starikovskaya

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

4 Citations (Scopus)
233 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationString Processing and Information Retrieval
Subtitle of host publication22nd International Symposium, SPIRE 2015, London, UK, September 1-4, 2015, Proceedings
PublisherSpringer International Publishing AG
Number of pages12
ISBN (Electronic)9783319238265
ISBN (Print)9783319238258
Publication statusPublished - 5 Sept 2015
EventInternational Symposium on String Processing and Information Retrieval - , United Kingdom
Duration: 1 Sept 2015 → …

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing
ISSN (Print)0302-9743


ConferenceInternational Symposium on String Processing and Information Retrieval
Country/TerritoryUnited Kingdom
Period1/09/15 → …

Bibliographical note

Date of Acceptance: 21/01/2015


Dive into the research topics of 'Computing the Longest Unbordered Substring'. Together they form a unique fingerprint.

Cite this