Longest property-preserved common factor: A new string-processing framework - Archive ouverte HAL Access content directly
Journal Articles Theoretical Computer Science Year : 2020

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

(1) , (2) , (3, 4) , (1) , (3, 4) , (5, 4) , (3)
1
2
3
4
5

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.
Fichier principal
Vignette du fichier
LPPCF_journalVersion_TCS.pdf (824.26 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02956135 , version 1 (02-10-2020)

Identifiers

Cite

Lorraine A.K. Ayad, Giulia Bernardini, Roberto Grossi, Costas S Iliopoulos, Nadia Pisanti, et al.. Longest property-preserved common factor: A new string-processing framework. Theoretical Computer Science, 2020, 812, pp.244-251. ⟨10.1016/j.tcs.2020.02.012⟩. ⟨hal-02956135⟩

Collections

INRIA INRIA2
33 View
119 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More