Take the 2-minute tour ×  Construct a string by using only n
characters, the string should do not contain any consecutive
repeated pattern, in other words, the string must have not any
substring matching /(.+)\1/, what is the length l(n) of the
longest string S(n)?  n    S(n)    l(n) 1    a       1 2    aba
3 3    ?       ? 4    ?       ?  abcabacbabcabacabcac has none
consecutive repeated pattern,so l(3)>=20  share|improve this
question Could you explain the code? In your example "aba", it
seems that "a" is repeated. –  damiano Aug 26 '10 at 9:16
Another way to say this is that there are no identical
consecutive substrings. –  Dan Brumleve Aug 26 '10 at 9:30 add
comment  3 Answers  up vote 4 down vote accepted  A theorem of
Thue's (not Thue's theorem!) states that for $n = 3$ (and
therefore, also for larger $n$) an infinite sequence of
characters (chosen out of $n$) without repeated sub-sequences
(a.k.a square-free) exists.  Edit: here's a slightly related
reference: J.D. Currie's paper 'There are ternar