TY - GEN
T1 - Computing maximum number of runs in strings
AU - Kusano, Kazuhiko
AU - Narisawa, Kazuyuki
AU - Shinohara, Ayumi
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84867488003&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84867488003&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-34109-0_33
DO - 10.1007/978-3-642-34109-0_33
M3 - Conference contribution
AN - SCOPUS:84867488003
SN - 9783642341083
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 318
EP - 329
BT - String Processing and Information Retrieval - 19th International Symposium, SPIRE 2012, Proceedings
PB - Springer Verlag
T2 - 19th International Symposium on String Processing and Information Retrieval, SPIRE 2012
Y2 - 21 October 2012 through 25 October 2012
ER -