Longest property-preserved common factor

Lorraine A.K. Ayad, Giulia Bernardini, Roberto Grossi, Costas S. Iliopoulos, Nadia Pisanti*, Solon P. Pissis, Giovanna Rosone

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

In this paper we introduce a new family of string processing problems. We are given two or more strings and we are asked to compute a factor common to all strings that preserves a specific property and has maximal length. Here we consider two fundamental string properties: square-free factors and periodic factors under two different settings, one per property. In the first setting, we are given a string x and we are asked to construct a data structure over x answering the following type of on-line queries: given string y, find a longest square-free factor common to x and y. In the second setting, we are given k strings and an integer 1 < k’ ≤ k and we are asked to find a longest periodic factor common to at least k’ strings. We present linear-time solutions for both settings. We anticipate that our paradigm can be extended to other string properties.

Original languageEnglish
Title of host publicationString Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings
EditorsTravis Gagie, Alistair Moffat, Gonzalo Navarro, Ernesto Cuadros-Vargas
PublisherSpringer Verlag
Pages42-49
Number of pages8
ISBN (Print)9783030004781
DOIs
Publication statusPublished - 1 Jan 2018
Externally publishedYes
Event25th International Symposium on String Processing and Information Retrieval, SPIRE 2018 - Lima, Peru
Duration: 9 Oct 201811 Oct 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11147 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th International Symposium on String Processing and Information Retrieval, SPIRE 2018
CountryPeru
CityLima
Period9/10/1811/10/18

Keywords

  • Algorithms
  • Longest common factor
  • Periodicity
  • Squares

Fingerprint Dive into the research topics of 'Longest property-preserved common factor'. Together they form a unique fingerprint.

  • Cite this

    Ayad, L. A. K., Bernardini, G., Grossi, R., Iliopoulos, C. S., Pisanti, N., Pissis, S. P., & Rosone, G. (2018). Longest property-preserved common factor. In T. Gagie, A. Moffat, G. Navarro, & E. Cuadros-Vargas (Eds.), String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings (pp. 42-49). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11147 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-00479-8_4