Name
Abstract | ||
|---|---|---|
A factor W of a string X is called a cover of X, if X can be constructed by concatenations and superpositions of W. Breslauer (IPL, 1992) 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 log n)-time algorithm that computes the shortest cover of every cyclic shift of a string and an O(n)-time algorithm that computes the shortest among these covers. A related problem is the number of different lengths of shortest covers of cyclic shifts of the same string of length n. We show that this number is Omega(log n). |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/978-3-030-39881-1_7 | WALCOM: ALGORITHMS AND COMPUTATION (WALCOM 2020) |
Field | DocType | Volume |
Binary logarithm,Discrete mathematics,Combinatorics,Computer science,Prefix,Cyclic shift | Conference | 12049 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
0 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maxime Crochemore | 1 | 2655 | 281.75 |
| Costas S. Iliopoulos | 2 | 1534 | 167.43 |
| Jakub Radoszewski | 3 | 624 | 50.36 |
| Wojciech Rytter | 4 | 2290 | 181.52 |
| Juliusz Straszynski | 5 | 2 | 5.15 |
| Tomasz Waleń | 6 | 706 | 39.62 |
| Wiktor Zuba | 7 | 0 | 1.69 |