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 two fundamental string properties: square-free factors and periodic factors under two 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. We present linear-time solutions for both settings. We anticipate that our paradigm can be extended to other string properties.

Ayad, L., Bernardini, G., Grossi, R., Iliopoulos, C., Pisanti, N., Solon, P., et al. (2018). Longest Property-Preserved Common Factor. In String Processing and Information Retrieval (pp.42-49). Springer Verlag [10.1007/978-3-030-00479-8_4].

Longest Property-Preserved Common Factor

Bernardini, G;
2018

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 two fundamental string properties: square-free factors and periodic factors under two 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
paper
Algorithms; Longest common factor; Periodicity; Squares;
Longest common factor, Periodicity, Squares, Algorithms
English
25th International Symposium on String Processing and Information Retrieval, SPIRE 2018
2018
String Processing and Information Retrieval
9783030004781
2018
11147
42
49
none
Ayad, L., Bernardini, G., Grossi, R., Iliopoulos, C., Pisanti, N., Solon, P., et al. (2018). Longest Property-Preserved Common Factor. In String Processing and Information Retrieval (pp.42-49). Springer Verlag [10.1007/978-3-030-00479-8_4].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/207677
Citazioni
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
Social impact