Research output: Contribution to journal › Article

**Longest property-preserved common factor : A new string-processing framework.** / Ayad, Lorraine A.K.; Bernardini, Giulia; Grossi, Roberto; Iliopoulos, Costas S.; Pisanti, Nadia; Pissis, Solon P.; Rosone, Giovanna.

Research output: Contribution to journal › Article

Ayad, LAK, Bernardini, G, Grossi, R, Iliopoulos, CS, Pisanti, N, Pissis, SP & Rosone, G 2020, 'Longest property-preserved common factor: A new string-processing framework', *Theoretical Computer Science*, vol. 812, pp. 244-251. https://doi.org/10.1016/j.tcs.2020.02.012

Ayad, L. A. K., Bernardini, G., Grossi, R., Iliopoulos, C. S., Pisanti, N., Pissis, S. P., & Rosone, G. (2020). Longest property-preserved common factor: A new string-processing framework. *Theoretical Computer Science*, *812*, 244-251. https://doi.org/10.1016/j.tcs.2020.02.012

Ayad LAK, Bernardini G, Grossi R, Iliopoulos CS, Pisanti N, Pissis SP et al. Longest property-preserved common factor: A new string-processing framework. Theoretical Computer Science. 2020 Apr 6;812:244-251. https://doi.org/10.1016/j.tcs.2020.02.012

@article{fa765a7f8521485080ba4349090ba4ab,

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

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

U2 - 10.1016/j.tcs.2020.02.012

DO - 10.1016/j.tcs.2020.02.012

M3 - Article

AN - SCOPUS:85079372638

VL - 812

SP - 244

EP - 251

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -

King's College London - Homepage

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454