科研之友
微信
新浪微博
Facebook
分享链接
摘要
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, Sigma) = min{f (S): S is of length n, over alphabet Sigma}. Here, it is shown that %26lt;br%26gt;2f (n, (0, 1)) = n - o (n) %26lt;br%26gt;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.
- 出版日期2013-5
