How many runs can a string contain?
In 2000 Kolpakov and Kucherov showed that the maximum number ρ(n) of runs in any string x[1..n] is O(n), but their proof was nonconstructive and provided no specific constant of proportionality. At the same time, they presented experimental data to prompt the conjecture: ρ(n)<n. Recently, Rytter...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Published: |
Elsevier
2008
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/47398 |