Name
Abstract | ||
|---|---|---|
A run (also called maximal repetition) in a word is a non-extendable repetition. Finding the maximum number ρ(n) of runs in a string of length n is a challenging problem. Although it is known that ρ(n)≤1.029n for any n and there exists large n such that ρ(n)≥0.945n, the exact value of ρ(n) is still unknown. Several algorithms have been proposed to count runs in a string efficiently, and ρ(n) can be obtained for small n by these algorithms. In this paper, we focus on computing ρ(n) for given length parameter n, instead of exhaustively counting all runs for every string of length n. We report exact values of ρ(n) for binary strings for n≤66, together with the strings which contain ρ(n) runs. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-34109-0_33 | SPIRE |
Keywords | Field | DocType |
length parameter n,non-extendable repetition,maximal repetition,length n,small n,challenging problem,computing maximum number,maximum number,binary string,exact value | Discrete mathematics,Combinatorics,Existential quantification,Binary strings,Mathematics | Conference |
Volume | ISSN | Citations |
7608 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kazuhiko Kusano | 1 | 24 | 3.51 |
| Kazuyuki Narisawa | 2 | 33 | 6.82 |
| Ayumi Shinohara | 3 | 936 | 88.28 |