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

Материал из Википедии — свободной энциклопедии

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

А. Туэ доказал, что бесконечные бесквадратные слова существуют над любыми алфавитами из по крайней мере 3 букв. Один из простейших примеров бесконечного бесквадратного слова над алфавитом из 3 букв можно построить, если начать с слова $w 1 = 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 (n log(n))$ действий. Для этого нужно построить за $O (n)$ суффиксное дерево и сделать предварительные расчеты (см. наименьший общий предшественник), позволяющие за $O (1)$ находить по данным $x$ и $y$ наибольшее $l$ такое, что подстроки длины $l$ начинающиеся с позиций $x$ и $y$ совпадают. Также построим суффиксное дерево и выполним этим расчеты для обратной строки, чтобы по $x$ и $y$ находить длину наибольшей общей подстроки, заканчивающуюся в этих позициях.

После этого задача решается рекурсивно. Разобъем строку посередине и проверим каждую из половинок. Если в одной из них есть подслово вида $x x$ , то и исходная строка не является бесквадратной. Пусть $m$ — позиция начала второй половинки. Для всех длин $1\le s\le 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\le s\le n$ . Легко видеть, что если ни одна из процедур не нашла квадрата, то и позиция $m$ не может принадлежать никакому квадрату, а значит слово является бесквадратным. Поскольку после предварительных расчетов нахождение общей подстроки можно выполнить за $O (1)$ , то для проверки позиции $m$ алгоритму понадобиться $O (n)$ шагов. С учетом рекурсии получаем общую сложность алгоритма $O (n log(n))$ .

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

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

[править] Литература

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.