A regularity lemma and twins in words
: M Axenovich, Yu Person, S Puzynina
Publisher: elsevier
: 2013
: Journal of Combinatorial Theory, Series A
: 4
: 120
: 4
: 733
: 743
: 11
: 0097-3165
DOI: https://doi.org/10.1016/j.jcta.2013.01.001
We prove that in a word of length n over an alphabet of k letters there are l disjoints identical (scattered) subwords of length n/l/o(n) for l \geq k. E.g., any binary word of length n can be split into two identical subwords (referred to as twins) and, perhaps, a remaining subword of length o(n).