Name
Abstract | ||
|---|---|---|
A run is a maximal occurrence of a repetition $v$ with a period $p$ such that
$2p \le |v|$. The maximal number of runs in a string of length $n$ was studied
by several authors and it is known to be between $0.944 n$ and $1.029 n$. We
investigate highly periodic runs, in which the shortest period $p$ satisfies
$3p \le |v|$. We show the upper bound $0.5n$ on the maximal number of such runs
in a string of length $n$ and construct a sequence of words for which we obtain
the lower bound $0.406 n$. |
Year | Venue | Keywords |
|---|---|---|
2009 | Clinical Orthopaedics and Related Research | data structure,satisfiability,upper bound,discrete mathematics,lower bound |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Upper and lower bounds,Periodic graph (geometry),Mathematics | Journal | abs/0907.2 |
Citations | PageRank | References |
0 | 0.34 | 13 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maxime Crochemore | 1 | 2655 | 281.75 |
| Costas S. Iliopoulos | 2 | 1534 | 167.43 |
| Marcin Kubica | 3 | 629 | 29.26 |
| Jakub Radoszewski | 4 | 624 | 50.36 |
| Wojciech Rytter | 5 | 2290 | 181.52 |
| Tomasz Waleń | 6 | 706 | 39.62 |