Computing the longest unbordered substring

Paweł Gawrychowski, Gregory Kucherov, Benjamin Sach, Tatiana Starikovskaya

Результат исследований: Глава в книге, отчете, сборнике статейМатериалы для конференциирецензирование

4 Цитирования (Scopus)

Аннотация

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, n24}) 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(n log n) average-case running time and O(n2) worst-case running time, and the second algorithm has O(n1.5) worst-case running time.

Язык оригиналаАнглийский
Название основной публикацииString Processing and Information Retrieval - 22nd International Symposium, SPIRE 2015, Proceedings
РедакторыSimon J. Puglisi, Costas S. Iliopoulos, Emine Yilmaz
ИздательSpringer Verlag
Страницы246-257
Число страниц12
ISBN (печатное издание)9783319238258
DOI
СостояниеОпубликовано - 2015
Опубликовано для внешнего пользованияДа
Событие22nd International Symposium on String Processing and Information Retrieval, SPIRE 2015 - London, Великобритания
Продолжительность: 1 сент. 20154 сент. 2015

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том9309
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция22nd International Symposium on String Processing and Information Retrieval, SPIRE 2015
Страна/TерриторияВеликобритания
ГородLondon
Период1/09/154/09/15

Fingerprint

Подробные сведения о темах исследования «Computing the longest unbordered substring». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать