Longest property-preserved common factor

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

doi:10.1007/978-3-030-00479-8_4

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 proceeding › Conference contribution › Academic › peer-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 language	English
Title of host publication	String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings
Editors	Travis Gagie, Alistair Moffat, Gonzalo Navarro, Ernesto Cuadros-Vargas
Publisher	Springer Verlag
Pages	42-49
Number of pages	8
ISBN (Print)	9783030004781
DOIs	https://doi.org/10.1007/978-3-030-00479-8_4
Publication status	Published - 1 Jan 2018
Externally published	Yes
Event	25th International Symposium on String Processing and Information Retrieval, SPIRE 2018 - Lima, Peru Duration: 9 Oct 2018 → 11 Oct 2018

Publication series

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

Conference

Conference	25th International Symposium on String Processing and Information Retrieval, SPIRE 2018
Country/Territory	Peru
City	Lima
Period	9/10/18 → 11/10/18

Funding

Acknowledgements. Solon P. Pissis and Giovanna Rosone are partially supported by the Royal Society project IE 161274 “Processing uncertain sequences: combinatorics and applications”. Giovanna Rosone and Nadia Pisanti are partially supported by the project Italian MIUR-SIR CMACBioSeq (“Combinatorial methods for analysis and compression of biological sequences”) grant n. RBSI146R5L. Solon P. Pissis and Giovanna Rosone are partially supported by the Royal Society project IE 161274 “Processing uncertain sequences: combinatorics and applications”. Giovanna Rosone and Nadia Pisanti are partially supported by the project Italian MIUR-SIR CMACBioSeq (“Combinatorial methods for analysis and compression of biological sequences”) grant n. RBSI146R5L.

Funders	Funder number
Royal Society	IE 161274
Ministero dell’Istruzione, dell’Università e della Ricerca	RBSI146R5L

Keywords

Algorithms
Longest common factor
Periodicity
Squares

Access to Document

10.1007/978-3-030-00479-8_4

Persistent URL (handle)

Persistent link

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

Ayad, Lorraine A.K. ; Bernardini, Giulia ; Grossi, Roberto et al. / Longest property-preserved common factor. String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings. editor / Travis Gagie ; Alistair Moffat ; Gonzalo Navarro ; Ernesto Cuadros-Vargas. Springer Verlag, 2018. pp. 42-49 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{012fa09cadb44545b1ad5bd7cfcda1a1,

title = "Longest property-preserved common factor",

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{\textquoteright} ≤ k and we are asked to find a longest periodic factor common to at least k{\textquoteright} strings. We present linear-time solutions for both settings. We anticipate that our paradigm can be extended to other string properties.",

keywords = "Algorithms, Longest common factor, Periodicity, Squares",

author = "Ayad, \{Lorraine A.K.\} and Giulia Bernardini and Roberto Grossi and Iliopoulos, \{Costas S.\} and Nadia Pisanti and Pissis, \{Solon P.\} and Giovanna Rosone",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-030-00479-8\_4",

language = "English",

isbn = "9783030004781",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "42--49",

editor = "Travis Gagie and Alistair Moffat and Gonzalo Navarro and Ernesto Cuadros-Vargas",

booktitle = "String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings",

address = "Germany",

note = "25th International Symposium on String Processing and Information Retrieval, SPIRE 2018 ; Conference date: 09-10-2018 Through 11-10-2018",

}

Ayad, LAK, Bernardini, G, Grossi, R, Iliopoulos, CS, Pisanti, N, Pissis, SP & 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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11147 LNCS, Springer Verlag, pp. 42-49, 25th International Symposium on String Processing and Information Retrieval, SPIRE 2018, Lima, Peru, 9/10/18. https://doi.org/10.1007/978-3-030-00479-8_4

Longest property-preserved common factor. / Ayad, Lorraine A.K.; Bernardini, Giulia; Grossi, Roberto et al.
String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings. ed. / Travis Gagie; Alistair Moffat; Gonzalo Navarro; Ernesto Cuadros-Vargas. Springer Verlag, 2018. p. 42-49 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11147 LNCS).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Longest property-preserved common factor

AU - Ayad, Lorraine A.K.

AU - Bernardini, Giulia

AU - Grossi, Roberto

AU - Iliopoulos, Costas S.

AU - Pisanti, Nadia

AU - Pissis, Solon P.

AU - Rosone, Giovanna

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

KW - Algorithms

KW - Longest common factor

KW - Periodicity

KW - Squares

UR - https://www.scopus.com/pages/publications/85054783081

UR - https://www.scopus.com/pages/publications/85054783081#tab=citedBy

U2 - 10.1007/978-3-030-00479-8_4

DO - 10.1007/978-3-030-00479-8_4

M3 - Conference contribution

AN - SCOPUS:85054783081

SN - 9783030004781

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 42

EP - 49

BT - String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings

A2 - Gagie, Travis

A2 - Moffat, Alistair

A2 - Navarro, Gonzalo

A2 - Cuadros-Vargas, Ernesto

PB - Springer Verlag

T2 - 25th International Symposium on String Processing and Information Retrieval, SPIRE 2018

Y2 - 9 October 2018 through 11 October 2018

ER -

Ayad LAK, Bernardini G, Grossi R, Iliopoulos CS, Pisanti N, Pissis SP et al. Longest property-preserved common factor. In Gagie T, Moffat A, Navarro G, Cuadros-Vargas E, editors, String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings. Springer Verlag. 2018. p. 42-49. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-00479-8_4

Longest property-preserved common factor

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this