Longest Property-Preserved Common Factor

Abstract : 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.
Type de document :
Communication dans un congrès
International Symposium on String Processing and Information Retrieval, 2018, Lima, Peru
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01921603
Contributeur : Marie-France Sagot <>
Soumis le : mardi 13 novembre 2018 - 21:18:39
Dernière modification le : jeudi 7 février 2019 - 16:31:39
Document(s) archivé(s) le : jeudi 14 février 2019 - 16:51:17

Fichier

1810.02099.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01921603, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

7

Téléchargements de fichiers

20