Бесповторное слово

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

А. Туэ доказал, что бесконечные бесквадратные слова существуют над любыми алфавитами из по крайней мере 3 букв. Один из простейших примеров бесконечного бесквадратного слова над алфавитом из 3 букв можно построить, если начать с слова w₁ = a и далее из слова w_i получать слово w_{i + 1} с помощью замен «a»->«abcab», «b»->«acabcb», «c»->«acbcacb». Каждое следующее слово будет содержать в себе предыдущее, что позволяет построить бесконечное слово «abcabacabcbacbcacbabcabacabcb…». Число бесквадратных слов длины n растет экспоненциально от n. Показатель экспоненты s на данный момент оценивается как $1.109999\dots=65^{1/40}<s<8416550317984^{1/108}=1.317227\dots$([1]).

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

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

После этого задача решается рекурсивно. Разобъем строку посередине и проверим каждую из половинок. Если в одной из них есть подслово вида xx, то и исходная строка не является бесквадратной. Пусть m — позиция начала второй половинки. Для всех длин $1\le s\le n$ найдем длину l₁ общей подстроки для позиций m и m + s, а также длину l₂ общей подстроки начинающейся в позициях m и m + s но идущей в обратном направлении. Если l₁ + l₂ > s, то подслова длины s, начинающиеся с позиций m − l₁ + 1 и m + s − l₁ + 1 совпадают, а значит слово не является бесквадратным. После этого проделаем эту же процедуру для позиций m и m − s для всех $1\le s\le n$. Легко видеть, что если ни одна из процедур не нашла квадрата, то и позиция m не может принадлежать никакому квадрату, а значит слово является бесквадратным. Поскольку после предварительных расчетов нахождение общей подстроки можно выполнить за O(1), то для проверки позиции m алгоритму понадобиться O(n) шагов. С учетом рекурсии получаем общую сложность алгоритма O(nlog(n)).

Этот алгоритм легко обобщается на поиски повторений любой длины: достаточно заменить условие l₁ + l₂ > s на условие l₁ + l₂ > (k − 1)s для поиска строк, повторяющихся k раз подряд.

Если вместо суффиксных деревьев использовать более простые суффиксные массивы и вместо алгоритма поиска общей подстроки за O(1) использовать более простой алгоритм за O(log(n)) на основе промежуточных результатов построения суффиксного массива, то этот алгоритм будет работать за O(nlog²(n)). Это не сильно хуже, учитывая значительное упрощение алгоритма в этом случае.

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

• Начиная с "а" применять замены: a -> "abcab"; b -> "acabcb"; c -> "acbcacb" (А. Туэ, 1917)
• Начиная с "а" применять замены: a -> "abacb"; b -> "abcbac"; c -> "abcacbc" (А. Туэ, 1917)
• Начиная с "а" применять замены: a -> "abcbacbcabcba"; b -> "bcacbacabcacb"; c -> "cabacbabcabac" (J. Leech, c.1957)
• Последовательность Морса-Туэ, если её разделить на группы по 2 цифры и каждую группу заменить соответствующим образом: 01 -> a, 10 -> b, 00 -> c, 11 -> c.

Литература

• 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.(англ.)