Бесквадратное слово

Бесквадра́тное сло́во (англ. square-free word) — слово, в котором никакое подслово не повторяется подряд 2 раза (т.е. это слово нельзя представить в виде yxxz, где x, у и z — некоторые подслова).

А. Туэ доказал, что бесконечные бесквадратные слова существуют над любыми алфавитами из по крайней мере 3 букв. Один из простейших примеров бесконечного бесквадратного слова над алфавитом из 3 букв можно построить, если начать с слова $w_{1}=a$ и далее из слова $w_{i}$ получать слово $w_{i+1}$ с помощью замен «a»->«abcab», «b»->«acabcb», «c»->«acbcacb». Каждое следующее слово будет содержать в себе предыдущее, что позволяет построить бесконечное слово «abcabacabcbacbcacbabcabacabcb…».

Число бесквадратных слов из трёх букв длины $n$ образует последовательность A006156 в OEIS. Она растёт экспоненциально от $n$, а показатель экспоненты равен $1.3017...$.

Проверка слова на бесквадратность

Если есть слово $w$ длины $n$, то можно проверить, является ли оно бесквадратным за $O(n\log(n))$ действий. Для этого нужно построить за $O(n)$ суффиксное дерево и сделать предварительные расчеты (см. наименьший общий предшественник), позволяющие за $O(1)$ находить по данным $x$ и $y$ наибольшее $l$ такое, что подстроки длины $l$, начинающиеся с позиций $x$ и $y$, совпадают. Также построим суффиксное дерево и выполним этим расчеты для обратной строки, чтобы по $x$ и $y$ находить длину наибольшей общей подстроки, заканчивающуюся в этих позициях.

После этого задача решается рекурсивно. Разобьем строку посередине и проверим каждую из половинок. Если в одной из них есть подслово вида $xx$, то и исходная строка не является бесквадратной. Пусть $m$ — позиция начала второй половинки. Для всех длин $1\leq s\leq n$ найдем длину $l_{1}$ общей подстроки для позиций $m$ и $m+s$, а также длину $l_{2}$ общей подстроки, начинающейся в позициях $m$ и $m+s$, но идущей в обратном направлении. Если $l_{1}+l_{2}>s$, то подслова длины $s$, начинающиеся с позиций $m-l_{1}+1$ и $m+s-l_{1}+1$, совпадают, а значит, слово не является бесквадратным. После этого проделаем эту же процедуру для позиций $m$ и $m-s$ для всех $1\leq s\leq n$. Легко видеть, что если ни одна из процедур не нашла квадрата, то и позиция $m$ не может принадлежать никакому квадрату, а значит, слово является бесквадратным. Поскольку после предварительных расчетов нахождение общей подстроки можно выполнить за $O(1)$, то для проверки позиции $m$ алгоритму понадобится $O(n)$ шагов. С учётом рекурсии получаем общую сложность алгоритма $O(n\log(n))$.

Этот алгоритм легко обобщается на поиски повторений любой длины: достаточно заменить условие $l_{1}+l_{2}>s$ на условие $l_{1}+l_{2}>(k-1)s$ для поиска строк, повторяющихся $k$ раз подряд.

Если вместо суффиксных деревьев использовать более простые суффиксные массивы и для поиска общей подстроки на основе промежуточных результатов построения суффиксного массива мы посчитаем lcp строк и построим sparse table (ну или линейное rmq, но это сложнее), то этот алгоритм будет работать за $O(n\log(n))$. Таким образом алгоритм заметно упрощается.

Примеры бесквадратных бесконечных последовательностей

• Начиная с «а» применять замены: a -> «abcab»; b -> «acabcb»; c -> «acbcacb» (А. Туэ, 1917)
• Начиная с «а» применять замены: a -> «abcbacbcabcba»; b -> «bcacbacabcacb»; c -> «cabacbabcabac» (J. Leech, c.1957)
• Также из последовательности Морса-Туэ можно получить бесконечное бесквадратное слово, если в этой последовательности для каждой единицы отметить, сколько нулей размещено после неё подряд. Если после единицы стоит ещё одна единица, пишем a. Если стоит один ноль, то пишем b. Если два нуля, пишем c. Больше двух нулей подряд встретиться не может. Поэтому полученное слово содержит буквы только трёх видов. Последовательность Морса-Туэ начинается следующим образом: 0110100110010110... Значит, начальные символы указанного слова выглядят так: abcacba...

Литература

• Allouche, J.-P. and Shallit, J. «Repetition in Words.» § 1.6 in Automatic Sequences: Theory, Applications, Generalizations. Cambridge, England: Cambridge University Press, pp. 14–16, 2003.
• Baake, M.; Elser, V.; and Grimm, U. «The Entropy of Square-Free Words.» 8 Sep 1998. http://arxiv.org/abs/math-ph/9809010/.
• Bean, D. R.; Ehrenfeucht, A.; and McNulty, G. F. «Avoidable Patterns in Strings of Symbols.» Pacific J. Math. 85, 261—294, 1979.
• Berstel, J. and Reutenauer, C. «Square-Free Words and Idempotent Semigroups.» In Combinatorics on Words (Ed. M. Lothaire). Reading, MA: Addison-Wesley, pp. 18–38, 1983.
• Brandenburg, F.-J. «Uniformly Growing th Power-Free Homomorphisms.» Theor. Comput. Sci. 23, 69-82, 1983.
• Brinkhuis, J. «Non-Repetitive Sequences on Three Symbols.» Quart. J. Math. Oxford Ser. 2 34, 145—149, 1983.
• Crochemore, M. «Sharp Characterizations of Squarefree Morphisms.» Theor. Comput. Sic. 18, 221—226, 1982.
• Crochemore, M. «Tests sur les morphismes faiblement sans carré.» In Combinatorics on Words (Ed. L. J. Cummings). Toronto: Academic Press, pp. 63–89, 1983.
• Finch, S. R. «Pattern-Free Word Constants.» § 5.17 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 367–371, 2003.
• Kobayashi, Y. «Repetition-Free Words.» Theor. Comput. Sci. 44, 175—197, 1986.
• Leconte, M. «th Power-Free Codes.» In Automata on Infinite Words (Ed. M. Nivat and D. Perrin). Berlin: Springer-Verlag, pp. 172–178, 1985.
• Noonan, J. and Zeilberger, D. «The Goulden-Jackson Cluster Method: Extensions, Applications, and Implementations.» J. Differ. Eq. Appl. 5, 355—377, 1999.
• Pleasants, P. A. B. «Nonrepetitive Sequences.» Proc. Cambridge Philos. Soc. 68, 267—274, 1970.
• Restivo, A. and Salemi, S. «Overlap-Free Words on Two Symbols.» In Automata on Infinite Words (Ed. M. Nivat and D. Perrin). New York: Springer-Verlag, pp. 198–206, 1985.
• Sloane, N. J. A. Sequences A006156/M2550 and A051041 in «The On-Line Encyclopedia of Integer Sequences.»
• Thue, A. «Über unendliche Zeichenreihen.» Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. Christiana 7, 1-22, 1906. Reprinted in Nagell, T.; Selberg, A.; Selberg, S.; and Thalberg, K. (Eds.). Selected Mathematical Papers of Axel Thue. Oslo, Norway: Universitetsforlaget, pp. 139–158, 1977.
• Thue, A. «Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen.» Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. Christiana 1, 1-67, 1912. Reprinted in Nagell, T.; Selberg, A.; Selberg, S.; and Thalberg, K. (Eds.). Selected Mathematical Papers of Axel Thue. Oslo, Norway: Universitetsforlaget, pp. 413–477, 1977.

Ссылки

• Weisstein, Eric W. Squarefree Word (англ.) на сайте Wolfram MathWorld.