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

Бесквадратное слово — слово, в котором никакое подслово не повторяется подряд 2 раза (т.е. это слово нельзя представить в виде yxxz, где x, у и z — некоторые подслова). А. Туэ доказал, что бесконечные бесквадратные слова существуют над любыми алфавитами из по крайней мере 3 букв. Один из простейших примеров бесконечного бесквадратного слова над алфавитом из 3 букв можно построить, если начать с слова w1=a и далее из слова wi получать слово wi+1 с помощью замен \texttt«a»-\textgreater«abcab»,\ «b»-\textgreater«acabcb»,\ «c»-\textgreater«acbcacb». Каждое следующее слово будет содержать в себе предыдущее, что позволяет построить бесконечное слово \texttt«abcabacabcbacbcacbabcabacabcb\ldots». Число бесквадратных слов длины n растет экспоненциально от n. Показатель экспоненты s на данный момент оценивается как $1.109999\dots=65^{1/40}1).

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

Если есть слово w длины n, то можно проверить, является ли оно бесквадратным за O(nlog(n)) действий. Для этого нужно построить за O(n) суффиксное дерево и сделать предварительные расчеты (см. наименьший общий предшественник), позволяющие за O(1) находить по данным x и y наибольшее l такое, что подстроки длины l, начинающиеся с позиций x и y, совпадают. Также построим суффиксное дерево и выполним этим расчеты для обратной строки, чтобы по x и y находить длину наибольшей общей подстроки, заканчивающуюся в этих позициях. После этого задача решается рекурсивно. Разобъем строку посередине и проверим каждую из половинок. Если в одной из них есть подслово вида xx, то и исходная строка не является бесквадратной. Пусть m — позиция начала второй половинки. Для всех длин 1sn найдем длину l1 общей подстроки для позиций m и m+s, а также длину l2 общей подстроки, начинающейся в позициях m и m+s, но идущей в обратном направлении. Если l1+l2>s, то подслова длины s, начинающиеся с позиций ml1+1 и m+sl1+1, совпадают, а значит, слово не является бесквадратным. После этого проделаем эту же процедуру для позиций m и ms для всех 1sn. Легко видеть, что если ни одна из процедур не нашла квадрата, то и позиция m не может принадлежать никакому квадрату, а значит, слово является бесквадратным. Поскольку после предварительных расчетов нахождение общей подстроки можно выполнить за O(1), то для проверки позиции m алгоритму понадобится O(n) шагов. С учётом рекурсии получаем общую сложность алгоритма O(nlog(n)). Этот алгоритм легко обобщается на поиски повторений любой длины: достаточно заменить условие l1+l2>s на условие l1+l2>(k1)s для поиска строк, повторяющихся k раз подряд. Если вместо суффиксных деревьев использовать более простые суффиксные массивы и вместо алгоритма поиска общей подстроки за O(1) использовать более простой алгоритм за O(log(n)) на основе промежуточных результатов построения суффиксного массива, то этот алгоритм будет работать за O(nlog2(n)). Это не сильно хуже, учитывая значительное упрощение алгоритма в этом случае.

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


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