Longest Property-Preserved Common Factor - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

Longest Property-Preserved Common Factor

Résumé

In this paper we introduce a new family of string processing problems. We are given two or more strings and we are asked to compute a factor common to all strings that preserves a specific property and has maximal length. Here 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 on-line queries: given 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 setting, 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. We anticipate that our paradigm can be extended to other string properties or settings.
Fichier principal
Vignette du fichier
1810.02099.pdf (425.13 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01921603 , version 1 (13-11-2018)

Identifiants

  • HAL Id : hal-01921603 , version 1

Citer

Lorraine a K Ayad, Giulia Bernardini, Roberto P Grossi, Costas S. Iliopoulos, Nadia Pisanti, et al.. Longest Property-Preserved Common Factor. International Symposium on String Processing and Information Retrieval, 2018, Lima, Peru. ⟨hal-01921603⟩

Collections

INRIA INRIA2
37 Consultations
130 Téléchargements

Partager

Gmail Facebook X LinkedIn More