Longest property-preserved common factor: A new string-processing framework

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

doi:10.1016/j.tcs.2020.02.012

Longest property-preserved common factor: A new string-processing framework

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: Contribution to Journal › Article › Academic › peer-review

Abstract

We introduce a new family of string processing problems. Given two or more strings, we are asked to compute a factor common to all strings that preserves a specific property and has maximal length. We consider three fundamental string properties: square-free factors, periodic factors, and palindromic factors under three 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 online queries: given a 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. In the third one, we are given two strings and we are asked to find a longest palindromic factor common to the two strings. We present linear-time solutions for all settings. This is a full and extended version of a paper from SPIRE 2018.

Original language	English
Pages (from-to)	244-251
Number of pages	8
Journal	Theoretical Computer Science
Volume	812
DOIs	https://doi.org/10.1016/j.tcs.2020.02.012
Publication status	Published - 6 Apr 2020
Externally published	Yes

Funding

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 MIUR -SIR grant n. RBSI146R5L , CMACBioSeq: “Combinatorial methods for analysis and compression of biological sequences”. Roberto Grossi is partially supported by MIUR Grant n. 20174LF3T8 AHeAD : “efficient Algorithms for HArnessing networked Data”.

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

Keywords

Palindromic factors
Periodic factors
Square-free factors

Access to Document

10.1016/j.tcs.2020.02.012

Persistent URL (handle)

Persistent link

Cite this

@article{656b2ee141a840928bc092282d49e571,

title = "Longest property-preserved common factor: A new string-processing framework",

abstract = "We introduce a new family of string processing problems. Given two or more strings, we are asked to compute a factor common to all strings that preserves a specific property and has maximal length. We consider three fundamental string properties: square-free factors, periodic factors, and palindromic factors under three 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 online queries: given a 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 and we are asked to find a longest periodic factor common to at least k′ strings. In the third one, we are given two strings and we are asked to find a longest palindromic factor common to the two strings. We present linear-time solutions for all settings. This is a full and extended version of a paper from SPIRE 2018.",

keywords = "Palindromic factors, Periodic factors, Square-free factors",

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

month = apr,

day = "6",

doi = "10.1016/j.tcs.2020.02.012",

language = "English",

volume = "812",

pages = "244--251",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Longest property-preserved common factor

T2 - A new string-processing framework

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 - 2020/4/6

Y1 - 2020/4/6

N2 - We introduce a new family of string processing problems. Given two or more strings, we are asked to compute a factor common to all strings that preserves a specific property and has maximal length. We consider three fundamental string properties: square-free factors, periodic factors, and palindromic factors under three 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 online queries: given a 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 and we are asked to find a longest periodic factor common to at least k′ strings. In the third one, we are given two strings and we are asked to find a longest palindromic factor common to the two strings. We present linear-time solutions for all settings. This is a full and extended version of a paper from SPIRE 2018.

AB - We introduce a new family of string processing problems. Given two or more strings, we are asked to compute a factor common to all strings that preserves a specific property and has maximal length. We consider three fundamental string properties: square-free factors, periodic factors, and palindromic factors under three 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 online queries: given a 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 and we are asked to find a longest periodic factor common to at least k′ strings. In the third one, we are given two strings and we are asked to find a longest palindromic factor common to the two strings. We present linear-time solutions for all settings. This is a full and extended version of a paper from SPIRE 2018.

KW - Palindromic factors

KW - Periodic factors

KW - Square-free factors

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

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

U2 - 10.1016/j.tcs.2020.02.012

DO - 10.1016/j.tcs.2020.02.012

M3 - Article

AN - SCOPUS:85079372638

SN - 0304-3975

VL - 812

SP - 244

EP - 251

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Longest property-preserved common factor: A new string-processing framework

Abstract

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this