King's College London

Research portal

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

Research output: Contribution to journalArticle

Standard

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.

In: Theoretical Computer Science, Vol. 812, 06.04.2020, p. 244-251.

Research output: Contribution to journalArticle

Harvard

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

APA

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

Vancouver

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

Author

Ayad, Lorraine A.K. ; Bernardini, Giulia ; Grossi, Roberto ; Iliopoulos, Costas S. ; Pisanti, Nadia ; Pissis, Solon P. ; Rosone, Giovanna. / Longest property-preserved common factor : A new string-processing framework. In: Theoretical Computer Science. 2020 ; Vol. 812. pp. 244-251.

Bibtex Download

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

}

RIS (suitable for import to EndNote) Download

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 -

View graph of relations

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