Computing the Longest Unbordered Substring
| Autor: | Gregory Kucherov, Benjamin Sach, Paweł Gawrychowski, Tatiana Starikovskaya |
|---|---|
| Přispěvatelé: | Institute of Informatics [Warsaw], Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW)-University of Warsaw (UW), Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), University of Bristol [Bristol], Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM) |
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: | |
| Zdroj: | Proc. of the 22nd International Symposium on String Processing and Information Retrieval (SPIRE), September 1-4, 2015, London, UK Proc. of the 22nd International Symposium on String Processing and Information Retrieval (SPIRE), September 1-4, 2015, London, UK, Sep 2015, London, United Kingdom. pp.12, ⟨10.1007/978-3-319-23826-5_24⟩ Gawrychowski, P, Kucherov, G, Sach, B G & Starikovskaya, T 2015, Computing the Longest Unbordered Substring . in String Processing and Information Retrieval : 22nd International Symposium, SPIRE 2015, London, UK, September 1-4, 2015, Proceedings . Lecture Notes in Computer Science, vol. 9309, Springer International Publishing AG, pp. 246-257, International Symposium on String Processing and Information Retrieval, United Kingdom, 1/09/15 . https://doi.org/10.1007/978-3-319-23826-5_24 String Processing and Information Retrieval ISBN: 9783319238258 SPIRE |
| DOI: | 10.1007/978-3-319-23826-5_24⟩ |
| Popis: | 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.i¾ź[CPM 2015], where the authors showed that the average-case running time of the simple, border-array based algorithm can be bounded by $$\mathcal {O}\max \{n, n^2/\sigma ^4\}$$ for $$\sigma $$ being the size of the alphabet. The worst-case running time remained $$\mathcal {O}n^2$$. Here we propose two algorithms, both presenting substantial theoretical improvements to the result of [11]. The first algorithm has $$\mathcal {O}n \log n$$ average-case running time and $$\mathcal {O}n^2$$ worst-case running time, and the second algorithm has $$\mathcal {O}n^{1.5}$$ worst-case running time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|