Name
Abstract | ||
|---|---|---|
A run is an inclusion maximal occurrence in a string (as a subinterval) of a repetition v with a period p such that 2p ≤ |v|. The exponent of a run is defined as |v|/p and is ≥ 2. We show new bounds on the maximal sum of exponents of runs in a string of length n. Our upper bound of 4.1 n is better than the best previously known proven bound of 5.6 n by Crochemore & Ilie (2008). The lower bound of 2.035 n, obtained using a family of binary words, contradicts the conjecture of Kolpakov & Kucherov (1999) that the maximal sum of exponents of runs in a string of length n is smaller than 2n. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.jda.2011.12.016 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
maximal sum,repetition v,period p,inclusion maximal occurrence | Journal | 14, |
ISSN | Citations | PageRank |
1570-8667 | 6 | 0.63 |
References | Authors | |
15 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maxime Crochemore | 1 | 2655 | 281.75 |
| Marcin Kubica | 2 | 629 | 29.26 |
| Jakub Radoszewski | 3 | 624 | 50.36 |
| Wojciech Rytter | 4 | 2290 | 181.52 |
| Tomasz Waleń | 5 | 706 | 39.62 |