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 -