History

Please fill in your query. A complete syntax description you will find on the General Help page.
Distinct squares in run-length encoded strings. (English)
Theor. Comput. Sci. 411, No. 49, 4235-4241 (2010).
Summary: Squares are strings of the form $ww$, where $w$ is any nonempty string. Two squares $ww$ and $w^{\prime} w^{\prime}$ are of different types if and only if $w\neq w^{\prime}$. {\it A. S. Fraenkel} and {\it J. Simpson} [“How many squares can a string contain?”, J. Comb. Theory, Ser. A 82, No.~1, 112‒120 (1998; Zbl 0910.05001)] proved that the number of square types contained in a string of length $n$ is bounded by $O(n)$. The set of all different square types contained in a string is called the vocabulary of the string. If a square can be obtained by a series of successive right-rotations from another square, then we say the latter covers the former. A square is called a $c$-square if no square with a smaller index can cover it and it is not a trivial square. The set containing all $c$-squares is called the covering set. Note that every string has a unique covering set. Furthermore, the vocabulary of the covering set is called $c$-vocabulary. In this paper, we prove that the cardinality of $c$-vocabulary in a string is less than $\frac{14}{3}N$, where $N$ is the number of runs in this string.