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

SN - 0304-3975

VL - 812

SP - 244

EP - 251

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -