A regularity lemma and twins in words

For a word S, let f ( S ) be the largest integer m such that there are two disjoint identical (scattered) subwords of length m. Let f ( n , Σ ) = min { f ( S ) : S is of length n , over alphabet Σ } . Here, it is shown that 2 f ( n , { 0 , 1 } ) = n − o ( n ) using the regularity lemma for words. In other words, 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 ) . A similar result is proven for k identical subwords of a word over an alphabet with at most k letters.