Name
Abstract | ||
|---|---|---|
A substring w[i..j] in w is called a repetition of period p if w[k] - w[k + p] for any i <= k <= j - p. Especially, a maximal repetition, which cannot be extended neither to left nor to right, is called a run.The ratio of the length of the run to its period, i.e. j-i+1/p, is called an exponent. The sum of exponents of runs in a string is of interest. The maximal value of the sum is still unknown, and the current upper bound is 2:9n given by Crochemore and Ilie, where n is the length of a string. In this paper we show a closed formula which exactly expresses the average value of it for any n and any alphabet size, and the limit of this value per unit length as n approaches infinity. For binary strings, the limit value is approximately 1.13103. We also show the average number of squares in a string of length n and its limit value. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1142/S0129054109007078 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | Field | DocType |
Combinatorics on words, run, repetition | Discrete mathematics,Substring,Combinatorics,Exponent,Upper and lower bounds,Binary strings,Infinity,Mathematics,Combinatorics on words,Alphabet | Journal |
Volume | Issue | ISSN |
20 | 6 | 0129-0541 |
Citations | PageRank | References |
2 | 0.38 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kazuhiko Kusano | 1 | 24 | 3.51 |
| Wataru Matsubara | 2 | 52 | 5.87 |
| Akira Ishino | 3 | 54 | 7.31 |
| Ayumi Shinohara | 4 | 936 | 88.28 |