Document Open Access Logo

Longest Unbordered Factor in Quasilinear Time

Authors Tomasz Kociumaka , Ritu Kundu , Manal Mohamed , Solon P. Pissis

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.70.pdf
  • Filesize: 0.57 MB
  • 13 pages

Document Identifiers

Author Details

Tomasz Kociumaka
  • Institute of Informatics, University of Warsaw, Warsaw, Poland
Ritu Kundu
  • Department of Informatics, King’s College London, London, UK
Manal Mohamed
  • Department of Informatics, King’s College London, London, UK
Solon P. Pissis
  • Department of Informatics, King’s College London, London, UK

Cite As Get BibTex

Tomasz Kociumaka, Ritu Kundu, Manal Mohamed, and Solon P. Pissis. Longest Unbordered Factor in Quasilinear Time. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 70:1-70:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ISAAC.2018.70

Abstract

A border u of a word w is a proper factor of w occurring both as a prefix and as a suffix. The maximal unbordered factor of w is the longest factor of w which does not have a border. Here an O(n log n)-time with high probability (or O(n log n log^2 log n)-time deterministic) algorithm to compute the Longest Unbordered Factor Array of w for general alphabets is presented, where n is the length of w. This array specifies the length of the maximal unbordered factor starting at each position of w. This is a major improvement on the running time of the currently best worst-case algorithm working in O(n^{1.5}) time for integer alphabets [Gawrychowski et al., 2015].

Subject Classification

ACM Subject Classification
  • Theory of computation → Pattern matching
Keywords
  • longest unbordered factor
  • factorisation
  • period
  • border
  • strings

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Michael A. Bender and Martin Farach-Colton. The LCA Problem Revisited. In Gaston H. Gonnet, Daniel Panario, and Alfredo Viola, editors, LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000, Proceedings, volume 1776 of Lecture Notes in Computer Science, pages 88-94. Springer, 2000. URL: http://dx.doi.org/10.1007/10719839_9.
  2. Patrick Hagge Cording and Mathias Bæk Tejs Knudsen. Maximal Unbordered Factors of Random Strings. In Shunsuke Inenaga, Kunihiko Sadakane, and Tetsuya Sakai, editors, String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings, volume 9954 of Lecture Notes in Computer Science, pages 93-96, 2016. URL: http://dx.doi.org/10.1007/978-3-319-46049-9_9.
  3. Maxime Crochemore, Christophe Hancart, and Thierry Lecroq. Algorithms on strings. Cambridge University Press, 2007. Google Scholar
  4. Maxime Crochemore and Lucian Ilie. Computing Longest Previous Factor in Linear Time and Applications. Inf. Process. Lett., 106(2):75-80, 2008. Google Scholar
  5. Maxime Crochemore, Lucian Ilie, Costas S. Iliopoulos, Marcin Kubica, Wojciech Rytter, and Tomasz Waleń. Computing the Longest Previous Factor. Eur. J. Comb., 34(1):15-26, 2013. Google Scholar
  6. Maxime Crochemore and Wojciech Rytter. Jewels of stringology. World Scientific, 2002. URL: http://dx.doi.org/10.1142/4838.
  7. Jean-Pierre Duval. Relationship between the period of a finite word and the length of its unbordered segments. Discrete Mathematics, 40(1):31-44, 1982. URL: http://dx.doi.org/10.1016/0012-365X(82)90186-8.
  8. Jean-Pierre Duval, Thierry Lecroq, and Arnaud Lefebvre. Linear computation of unbordered conjugate on unordered alphabet. Theor. Comput. Sci., 522:77-84, 2014. URL: http://dx.doi.org/10.1016/j.tcs.2013.12.008.
  9. Andrzej Ehrenfeucht and D. M. Silberger. Periodicity and unbordered segments of words. Discrete Mathematics, 26(2):101-109, 1979. URL: http://dx.doi.org/10.1016/0012-365X(79)90116-X.
  10. Pawel Gawrychowski, Gregory Kucherov, Benjamin Sach, and Tatiana A. Starikovskaya. Computing the Longest Unbordered Substring. In Costas S. Iliopoulos, Simon J. Puglisi, and Emine Yilmaz, editors, String Processing and Information Retrieval - 22nd International Symposium, SPIRE 2015, London, UK, September 1-4, 2015, Proceedings, volume 9309 of Lecture Notes in Computer Science, pages 246-257. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-23826-5_24.
  11. Stepan Holub and Dirk Nowotka. The Ehrenfeucht-Silberger problem. J. Comb. Theory, Ser. A, 119(3):668-682, 2012. URL: http://dx.doi.org/10.1016/j.jcta.2011.11.004.
  12. Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt. Fast Pattern Matching in Strings. SIAM J. Comput., 6(2):323-350, 1977. URL: http://dx.doi.org/10.1137/0206024.
  13. Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen. Efficient Data Structures for the Factor Periodicity Problem. In Liliana Calderón-Benavides, Cristina N. González-Caro, Edgar Chávez, and Nivio Ziviani, editors, String Processing and Information Retrieval - 19th International Symposium, SPIRE 2012, Cartagena de Indias, Colombia, October 21-25, 2012. Proceedings, volume 7608 of Lecture Notes in Computer Science, pages 284-294. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-34109-0_30.
  14. Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen. Internal Pattern Matching Queries in a Text and Applications. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 532-551. SIAM, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.36.
  15. Alexander Loptev, Gregory Kucherov, and Tatiana A. Starikovskaya. On Maximal Unbordered Factors. In Ferdinando Cicalese, Ely Porat, and Ugo Vaccaro, editors, Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 - July 1, 2015, Proceedings, volume 9133 of Lecture Notes in Computer Science, pages 343-354. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-19929-0_29.
  16. Milan Ruzic. Constructing Efficient Dictionaries in Close to Sorting Time. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, volume 5125 of Lecture Notes in Computer Science, pages 84-95. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-70575-8_8.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact