Computing Maximum Number of Runs in Strings.
String Processing and Information Retrieval - 19th International Symposium, SPIRE 2012, Cartagena de Indias, Colombia, October 21-25, 2012. Proceedings,
, pp.318-329
(2012), [peer-reviewed]
Event Date:
October 21-25, 2012
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…