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

Informatics

Università degli Studi di Milano-Bicocca
Dipartimento di Scienze dell’Uomo e dell’Ambiente, Sezione di Genetica, Via San Giuseppe 22, Universita ` di Pisa, Pisa 56127, Italy
Inria French Institute for Research in Computer Science and Automation

Research output: Contribution to journal › Conference paper › peer-review

4 Citations (Scopus)

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
Pages (from-to)	42-49
Number of pages	8
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOIs	https://doi.org/10.1007/978-3-030-00479-8_4
Publication status	Published - 1 Jan 2018
Event	25th International Symposium on String Processing and Information Retrieval, SPIRE 2018 - Lima, Peru Duration: 9 Oct 2018 → 11 Oct 2018

Keywords

Algorithms
Longest common factor
Periodicity
Squares

Access to Document

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

Cite this

@article{42363e52708e4efca607fc33bf3d8b3d,

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",

pages = "42--49",

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

issn = "0302-9743",

publisher = "Springer",

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

}

TY - JOUR

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

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

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

M3 - Conference paper

AN - SCOPUS:85054783081

SN - 0302-9743

SP - 42

EP - 49

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

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

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

Y2 - 9 October 2018 through 11 October 2018

ER -

Longest property-preserved common factor

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this