Name
Abstract | ||
|---|---|---|
A factor C of a string S is called a cover of S, if each position of S is contained in an occurrence of C. Breslauer (1992) [3] proposed a well-known O(n)-time algorithm that computes the shortest cover of every prefix of a string of length n. We show an O(n logn)time and O(n)-space algorithm that computes the shortest cover of every cyclic shift of a string of length n and an O(n)-time algorithm that computes the shortest among these covers. We also provide a combinatorial characterization of shortest covers of cyclic shifts of Fibonacci strings that leads to efficient algorithms for computing these covers.We further consider the bound on the number of different lengths of shortest covers of cyclic shifts of the same string of length n. We show that this number is Theta(logn) for Fibonacci strings. (C) 2021 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.tcs.2021.03.011 | THEORETICAL COMPUTER SCIENCE |
Keywords | DocType | Volume |
Cover, Quasiperiod, Seed, Fibonacci string | Journal | 866 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
0 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| maxime crochemore | 1 | 73 | 6.84 |
| Costas S. Iliopoulos | 2 | 0 | 0.34 |
| Jakub Radoszewski | 3 | 0 | 0.34 |
| wojciech rytter | 4 | 130 | 17.13 |
| Juliusz Straszynski | 5 | 2 | 5.15 |
| Tomasz Waleń | 6 | 706 | 39.62 |
| Wiktor Zuba | 7 | 0 | 1.69 |