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. 2f(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.
展开▼
机译：对于单词S，令f（S）为最大整数m，以便有两个长度为m的不相交的相同（分散）子词。令f（n，σ）= min {f（S）：S在字母σ}上的长度为n。在此显示。 2f（n，{0,1}）= n-o（n）使用单词的正则性引理。换句话说，任何长度为n的二进制字都可以分为两个相同的子字（称为对子），也可以拆分为长度为o（n）的剩余子字。对于在最多具有k个字母的字母表中的一个单词的k个相同子词，证明了类似的结果。
展开▼
