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.

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 - http://www.scopus.com/inward/record.url?scp=85054783081&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85054783081&partnerID=8YFLogxK

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