Report
Longest Property-Preserved Common Factor
| العنوان: | Longest Property-Preserved Common Factor |
|---|---|
| المؤلفون: | Ayad, Lorraine A. K, Bernardini, Giulia, Grossi, Roberto, Iliopoulos, Costas S., Pisanti, Nadia, Pissis, Solon P., Rosone, Giovanna |
| سنة النشر: | 2018 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms |
| الوصف: | 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'\leq 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. Comment: Extended version of SPIRE 2018 paper |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1810.02099 |
| رقم الانضمام: | edsarx.1810.02099 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |