Периодические слова. Теорема Файна-Вильфа.

Краткое резюме

Период слова — это допустимый сдвиг \(p\), при котором все символы на расстоянии \(p\) совпадают; минимальный период — наименьший такой сдвиг. Бордер слова — его наидлиннейший собственный префикс, одновременно являющийся суффиксом. Эти понятия эквивалентно кодируют одну и ту же структуру: если у слова длины \(n\) наибольший бордер имеет длину \(b\), то минимальный период равен \(n-b\). Overlap двух слов — наидлиннейший собственный суффикс первого слова, совпадающий с собственным префиксом второго.

Теорема Файна–Вильфа — центральный факт темы: если слово длины \(n\) имеет периоды \(p\) и \(q\), а \(n\ge p+q-\gcd(p,q)\), то \(\gcd(p,q)\) тоже является периодом; порог точен, то есть уменьшать его в общем случае нельзя. Для задач это означает три рабочих правила: длинные двойные периодичности схлопываются в НОД; минимальный период удобно искать через наибольший бордер; периодичность по данному \(p\) проверяется прямым сравнением за \(O(n)\), а минимальный период вычисляется за \(O(n)\) по бордер-массиву или эквивалентной префикс-функции.

Базовые понятия

Пусть \(A\) — конечный алфавит, \(w\in A^\*\) — конечное слово, \(|w|=n\). Слово \(u\) называется префиксом слова \(w\), если \(w=uv\) для некоторого слова \(v\); суффиксом — если \(w=vu\). Собственный префикс или суффикс — это префикс или суффикс, не совпадающий со всем словом. В задачах о периодичности обычно рассматривают только периоды \(p\) из диапазона \(1\le p\le n\); большие \(p\) тривиальны и обычно не несут новой информации.

Число \(p\), \(1\le p\le n\), называется периодом слова \(w=w*1\cdots w*n\), если [ wi=w1\le i\le n-p. ] Минимальный период обозначают }\quad\text{для всех \(\operatorname{per}(w)\). Любое непустое слово имеет период \(n\); если \(p\) — период, то любой его кратный \(kp\le n\) тоже период. Слово называется примитивным, если оно не представимо в виде \(u^k\) при \(k\ge2\).

Для двух слов \(x,y\) overlap \(\operatorname{overlap}(x,y)\) — это наидлиннейший собственный суффикс \(x\), который одновременно является собственным префиксом \(y\). Border слова \(w\) — это \(\operatorname{overlap}(w,w)\), то есть наидлиннейший собственный префикс слова, совпадающий с его суффиксом. Периоды и бордеры находятся во взаимно-однозначном соответствии: бордер длины \(b\) соответствует периоду \(n-b\). Поэтому [ \operatorname{per}(w)=n-\bigl|\operatorname{border}(w)\bigr|. ] Слово без непустых бордеров называют небодерным (unbordered); эквивалентно, его единственный период — \(n\).

Таблица сводит стандартные определения из классических источников по комбинаторике на словах и stringology.

Теорема Файна–Вильфа

В оригинальной статье 1965 года теорема была сформулирована для периодических последовательностей: если две последовательности с периодами \(h\) и \(k\) совпадают на \(h+k-\gcd(h,k)\) подряд идущих позициях, то они совпадают всюду; авторы также явно отмечают, что меньший порог в общем случае недостаточен. Эквивалентная и стандартная для теории слов формулировка такова: если конечное слово длины \(n\) имеет периоды \(p\) и \(q\) и [ n\ge p+q-\gcd(p,q), ] то \(\gcd(p,q)\) тоже является периодом слова.

Ниже дано комбинаторное доказательство, удобное именно для решения задач. Оно опирается на граф периодов: вершины — позиции слова, рёбра соединяют позиции, чьи равенства принуждаются периодами \(p\) и \(q\). Такой графический взгляд стандартен в современной литературе о Fine–Wilf-словах и периодических графах.

Лемма о графе периодов. Для фиксированных \(m,p,q\) определим граф \(G(m;p,q)\) на вершинах \(0,1,\dots,m-1\): вершины \(i\) и \(j\) соединены ребром тогда и только тогда, когда \(|i-j|=p\) или \(|i-j|=q\). Если слово \(w\) длины \(m\) имеет периоды \(p\) и \(q\), то на концах любого ребра стоят одинаковые символы. Следовательно, все позиции в одной связной компоненте графа содержат один и тот же символ.

Лемма о связности во взаимно простом случае. Пусть \(1\le p<q\), \(\gcd(p,q)=1\), \(m\ge p+q-1\). Тогда граф \(G(m;p,q)\) связен.

Доказательство леммы. Сначала рассмотрим базовый размер \(m\*0=p+q-1\). Достаточно показать, что любая вершина соединена с вершиной \(q-1\).

Для вершины \(r\in\{0,1,\dots,q-1\}\) рассмотрим последовательность остатков [ r,\quad r+p \pmod q,\quad r+2p \pmod q,\ \dots ] Так как \(\gcd(p,q)=1\), прибавление \(p\) по модулю \(q\) переставляет все классы вычетов, поэтому после не более чем \(q-1\) шагов мы попадём в остаток \(q-1\).

Нужно проверить, что каждый шаг по модулю \(q\) реализуется путём в графе. Если \(s+p<q\), то переход \(s\to s+p\) — просто ребро длины \(p\). Если \(s+p\ge q\), то [ s \to s+p \to s+p-q, ] где первый шаг имеет длину \(p\), а второй — длину \(q\). Значит, каждая вершина из множества \(\{0,\dots,q-1\}\) соединена с \(q-1\).

Теперь возьмём вершину \(t\in\{q,\dots,p+q-2\}\). Тогда \(t-p\in\{q-p,\dots,q-2\}\subseteq\{0,\dots,q-1\}\), то есть \(t\) соединена ребром длины \(p\) с уже рассмотренной вершиной. Следовательно, граф \(G(p+q-1;p,q)\) связен.

Если \(m>p+q-1\), то любая новая вершина \(t\ge p+q-1\) соединена ребром длины \(p\) с вершиной \(t-p<t\). Поэтому, добавляя вершины по одной, связность сохраняется. Лемма доказана.

Для наглядности полезно увидеть один конкретный маршрут. При \(p=5\), \(q=8\) вершина \(3\) идёт к \(7=q-1\) так:

Теорема Файна–Вильфа. Пусть слово \(w\) длины \(n\) имеет периоды \(p\) и \(q\). Если [ n\ge p+q-d,\qquad d=\gcd(p,q), ] то \(d\) является периодом \(w\).

Доказательство. Для удобства нумеруем позиции слова числами \(0,1,\dots,n-1\).

Сначала сведём общий случай к взаимно простому. Запишем [ p=d p_1,\qquad q=dq_1,\qquad \gcd(p_1,q_1)=1. ] Разобьём позиции слова по остаткам modulo \(d\). Для каждого \(r\in\{0,1,\dots,d-1\}\) рассмотрим подслово [ w^{(r)}=wr\,w\cdots ] из всех позиций с остатком }\,w_{r+2d\(r\) modulo \(d\).

Если \(w\) имеет период \(p=dp_1\), то в \(w^{(r)}\) сдвиг на \(p_1\) сохраняет буквы; значит, \(p_1\) — период слова \(w^{(r)}\). Аналогично \(q_1\) — период \(w^{(r)}\).

Оценим длину \(m*r=|w^{(r)}|\). Имеем [ m*r=\left\lfloor \frac{n-1-r}{d}\right\rfloor+1 \ge \left\lfloor \frac{n-d}{d}\right\rfloor+1 = \left\lfloor \frac{n}{d}\right\rfloor. ] Из условия \(n\ge p+q-d=d(p_1+q_1-1)\) получаем [ \left\lfloor \frac{n}{d}\right\rfloor \ge p_1+q_1-1. ] Следовательно, [ m*r\ge p_1+q_1-1. ]

Теперь применяем лемму о связности во взаимно простом случае к слову \(w^{(r)}\): его граф периодов с шагами \(p_1\) и \(q_1\) связен. По лемме о графе периодов это означает, что все символы в \(w^{(r)}\) одинаковы. Итак, во всяком фиксированном классе вычетов modulo \(d\) стоят одинаковые буквы.

Но это и есть определение того, что \(d\) — период слова \(w\): если две позиции отличаются на \(d\), то они лежат в одном и том же классе modulo \(d\), а значит, содержат одинаковый символ. Теорема доказана.

Порог в теореме точен. Уже оригинальная статья подчёркивает, что при меньшей длине утверждение в общем случае ложно. Простейший контрпример: слово aaabaaa длины \(7\) имеет периоды \(4\) и \(5\), но не период \(1\); здесь \(7=4+5-1-1\). Ещё один стандартный пример: abaababaaba длины \(11\) имеет периоды \(5\) и \(8\), но не период \(1\); здесь \(11=5+8-1-1\).

Следствия и алгоритмы

Самое полезное прикладное следствие — слабая лемма о периодичности: если \(p>q\) — периоды слова длины \(n\) и \(n\ge p+q\), то \(p-q\) тоже период. Доказательство буквально соответствует рисунку: для позиции \(i\) либо можно идти вперёд через \(i+p\), либо назад через \(i-q\); в обоих случаях получаем равенство \(w*i=w*{i+p-q}\). Повторяя этот шаг по аналогии с алгоритмом Евклида, часто быстро доходят до \(\gcd(p,q)\).

Ещё два стандартных следствия. Первое: если \(xy=yx\), то \(x\) и \(y\) являются целыми степенями одного и того же слова. Второе: непустое слово \(x\) примитивно тогда и только тогда, когда в \(x^2\) оно встречается только как префикс и как суффикс. Оба факта постоянно используются в задачах на уравнения в свободном моноиде и на доказательство примитивности.

Таблица собирает ровно те свойства, которые чаще всего нужны в задачах.

Для алгоритмов достаточно двух наблюдений. Проверка, является ли заданное \(p\) периодом, делается прямым сравнением \(w*i\) и \(w*{i+p}\) для всех \(1\le i\le n-p\); это требует \(O(n-p)\subseteq O(n)\) сравнений. Минимальный период эффективнее всего вычислять через длины наибольших бордеров всех префиксов. Классический алгоритм Border вычисляет такой массив за линейное время и не более чем за \(2n\) сравнений символов.

Ниже — удобная псевдозапись варианта алгоритма Border для слова \(w[0..n-1]\):

BORDER(w):
 n:= |w|
 b[0]:= -1
 i:= 0
 for j:= 1 to n-1:
 b[j]:= i
 while i >= 0 and w[j] != w[i]:
 i:= b[i]
 i:= i + 1
 b[n]:= i
 return b

После вычисления массива [ B(w)=b[n],\qquad \operatorname{per}(w)=n-b[n]. ] Эквивалентная, более привычная запись использует префикс-функцию \(\pi\) из алгоритма Кнута–Морриса–Пратта: [ \operatorname{per}(w)=n-\pi[n-1]. ] Если дополнительно \(\operatorname{per}(w)\mid n\), то слово является точной степенью своего префикса длины \(\operatorname{per}(w)\); если делимости нет, период всё равно существует, но разложение в целую степень отсутствует.

Связь с алгоритмами поиска подстроки прямая: те же бордеры и функция отказов лежат в основе алгоритма Кнута–Морриса–Пратта, который после линейной предобработки образца ищет его в тексте за линейное время по длине текста. В современной литературе по stringology периодичность и теорема Файна–Вильфа рассматриваются как один из главных структурных инструментов при анализе строковых алгоритмов.

Примеры и контрпримеры

Первые два слова удобны для ручного счета по определениям; последние два — минимальные по духу контрпримеры к попытке ослабить теорему Файна–Вильфа. Пример aabaabaa и связь между бордерами и периодами разбираются и в учебной литературе.

Практически полезно помнить два антишаблона мышления. Во-первых, «слово периодично» не означает «слово является точной степенью более короткого слова»: abababa имеет период \(2\), но не равно \(u^k\) ни для какого \(k\ge2\), потому что \(2\nmid7\). Во-вторых, из наличия двух периодов нельзя автоматически заключать, что их разность — период: для aaabaaa числа \(4\) и \(5\) — периоды, а \(1\) — нет, именно потому, что длина \(7\) недостаточна для применения слабой леммы или полной теоремы.

Типовые задачи с решениями

Ниже собраны восемь задач, покрывающих весь стандартный набор приёмов: определения, border–period correspondence, прямое применение теоремы Файна–Вильфа, контрпримеры, commutation lemma и линейное вычисление минимального периода. Методы в решениях опираются на определения и результаты из предыдущих разделов.

Задача 1. Найти \(\operatorname{overlap}(\texttt{abacaba},\texttt{acabaca})\), все бордеры слова aabaabaa и его минимальный период.

Решение. Собственные суффиксы слова abacaba: [ \texttt{a},\ \texttt{ba},\ \texttt{aba},\ \texttt{caba},\ \texttt{acaba},\ \texttt{bacaba}. ] Собственные префиксы слова acabaca: [ \texttt{a},\ \texttt{ac},\ \texttt{aca},\ \texttt{acab},\ \texttt{acaba},\ \texttt{acabac}. ] Самое длинное общее слово — acaba. Значит, [ \operatorname{overlap}(\texttt{abacaba},\texttt{acabaca})=\texttt{acaba}. ]

Для aabaabaa бордерами являются [ \varepsilon,\ \texttt{a},\ \texttt{aa},\ \texttt{aabaa}. ] Наибольший бордер имеет длину \(5\). Поэтому минимальный период равен [ \operatorname{per}(\texttt{aabaabaa})=8-5=3. ] Проверка по определению действительно даёт период \(3\): символы на расстоянии \(3\) совпадают во всех допустимых позициях.

Задача 2. Показать, что слово abababa периодично, но не является точной степенью более короткого слова.

Решение. У слова abababa есть период \(2\), поскольку [ a=b? \text{ нет,} ] но сравнивать нужно не соседние позиции, а позиции на расстоянии \(2\): [ w1=w3=w5=w7=\texttt{a},\qquad w2=w4=w*6=\texttt{b}. ] Следовательно, \(2\) — период. Меньшего периода нет, так как период \(1\) означал бы одинаковость всех букв.

Значит, [ \operatorname{per}(\texttt{abababa})=2. ] Однако \(2\nmid7\). Следовательно, слово нельзя записать в виде \(u^k\) с \(k\ge2\). Это стандартный контрпример к неверному тезису «минимальный период всегда делит длину».

Задача 3. Пусть слово длины \(18\) имеет периоды \(8\) и \(11\). Что можно о нём утверждать?

Решение. Здесь [ \gcd(8,11)=1,\qquad 8+11-\gcd(8,11)=18. ] Длина слова ровно равна порогу теоремы Файна–Вильфа, поэтому \(1\) — тоже период слова.

Период \(1\) означает, что все символы одинаковы. Следовательно, любое такое слово обязательно имеет вид [ a^{18} ] для некоторой буквы \(a\) алфавита. Других вариантов нет.

Задача 4. Доказать, что слово aaabaaa имеет периоды \(4\) и \(5\), но не период \(1\). Сделать вывод о точности оценки Файна–Вильфа для пары \((4,5)\).

Решение. Проверим период \(4\). Нужно сравнить пары [ (1,5),\ (2,6),\ (3,7). ] Во всех трёх случаях стоят буквы a, значит, \(4\) — период.

Проверим период \(5\). Нужно сравнить пары [ (1,6),\ (2,7). ] Снова получаем a=a и a=a, значит, \(5\) — период.

Но период \(1\) отсутствует, потому что слово не постоянно: в нём есть и a, и b. Следовательно, для \(p=4\), \(q=5\) длина \(7\) ещё недостаточна, хотя [ 7=4+5-1-1. ] Значит, порог \(4+5-1=8\) в теореме нельзя заменить на \(7\).

Задача 5. Слово длины \(23\) имеет периоды \(6\) и \(10\). Найти наименьший гарантированный период и описать все возможные такие слова.

Решение. Вычислим: [ d=\gcd(6,10)=2,\qquad 6+10-d=14. ] Так как \(23\ge14\), по теореме Файна–Вильфа число \(2\) является периодом.

Период \(2\) означает, что все нечётные позиции несут одну и ту же букву, а все чётные — одну и ту же букву. Поэтому общее описание таково: [ w=(xy)^{11}x ] для некоторых букв \(x,y\) алфавита. Если \(x=y\), то фактический минимальный период равен \(1\); если \(x\ne y\), то фактический минимальный период равен \(2\).

Задача 6. Доказать: если непустые слова \(x\) и \(y\) удовлетворяют \(xy=yx\), то они являются степенями одного общего слова.

Решение. Рассмотрим слово [ w=xy=yx. ] Сдвиг на \(|x|\) переводит \(xy\) в \(yx\), а так как \(xy=yx\), этот сдвиг оставляет слово неизменным. Значит, \(|x|\) — период \(w\). Аналогично \(|y|\) — тоже период \(w\).

Длина \(w\) равна \(|x|+|y|\), то есть точно равна порогу [ |x|+|y|-\gcd(|x|,|y|)+\gcd(|x|,|y|). ] Следовательно, по теореме Файна–Вильфа число [ d=\gcd(|x|,|y|) ] тоже является периодом слова \(w\).

Пусть \(t\) — префикс \(w\) длины \(d\). Поскольку \(d\) делит и \(|x|\), и \(|y|\), слово \(w\) разбивается на одинаковые блоки длины \(d\), равные \(t\). Тогда первые \(|x|\) символов образуют [ x=t^{|x|/d}, ] а следующие \(|y|\) символов — [ y=t^{|y|/d}. ] Итак, \(x\) и \(y\) — степени одного и того же слова \(t\).

Задача 7. Для слова abaababa дан бордер-массив [ b=(-1,0,0,1,1,2,3,2,3). ] Найти минимальный период и решить, является ли слово точной степенью более короткого слова.

Решение. Последний элемент массива равен длине наибольшего бордера: [ b[8]=3. ] Следовательно, [ \operatorname{per}(\texttt{abaababa})=8-3=5. ]

Итак, минимальный период равен \(5\). Чтобы слово было точной степенью более короткого слова, длина должна делиться на минимальный период. Но [ 5\nmid8. ] Значит, слово имеет период \(5\), но не является точной степенью слова длины \(5\).

Задача 8. Не пользуясь полной формой теоремы Файна–Вильфа, доказать, что слово длины \(14\) с периодами \(8\) и \(6\) имеет период \(2\).

Решение. Это ровно ситуация слабой леммы о периодичности: при \(p=8\), \(q=6\) и длине \(14\) выполнено [ 14\ge 8+6. ] Следовательно, \(8-6=2\) — период.

Если развернуть доказательство руками, то для \(1\le i\le 12\) нужно показать равенство \(w*i=w*{i+2}\).

Если \(1\le i\le 6\), то \(i+8\le14\), поэтому [ wi=w. ] Но позиции \(i+2\) и \(i+8\) отличаются на \(6\), а \(6\) — период, следовательно [ w{i+2}=w. ] Значит, \(w*i=w*{i+2}\).

Если \(7\le i\le12\), то \(i-6\ge1\), и по периоду \(6\) [ wi=w. ] Позиции \(i-6\) и \(i+2\) отличаются на \(8\), а \(8\) — период, значит [ w{i-6}=w. ] Снова \(w*i=w*{i+2}\). Итак, \(2\) действительно период.

Шпаргалка

| Что помнить | Формула или критерий | | ------------------------------------ | ---------------------------------------------------------------------- | ----------------------------- | --- | | Период слова | \(p\) — период \(\iff w*i=w*{i+p}\) для всех \(1\le i\le n-p\) | | Минимальный период | \(\operatorname{per}(w)=\min\{p:\ p\text{ — период}\}\) | | Бордер ↔ период | бордер длины \(b\) \(\iff\) период \(n-b\) | | Минимальный период через бордер | \(\operatorname{per}(w)=n-\bigl | \operatorname{border}(w)\bigr | \) | | Небордерность | \(\operatorname{border}(w)=\varepsilon \iff \operatorname{per}(w)=n\) | | Слабая периодичность | \(p>q,\ n\ge p+q \Rightarrow p-q\) — период | | Fine–Wilf | \(n\ge p+q-\gcd(p,q)\Rightarrow \gcd(p,q)\) — период | | Точная степень | \(w=u^k,\ k\ge2\) возможно только если \(\operatorname{per}(w)\mid n\) | | Проверка периода \(p\) | прямое сравнение \(w*i\) и \(w*{i+p}\), \(O(n)\) | | Минимальный период за линейное время | через Border/KMP: \(p\_{\min}=n-b[n]=n-\pi[n-1]\) |

Эта таблица конденсирует все основные факты, нужные для стандартных задач по теме.

Литература и первоисточники

1. Оригинальная статья Натан Дж. Файн и Герберт С. Уилф, Uniqueness theorems for periodic functions, Proceedings of the American Mathematical Society 16 (1965), 109–114. Это первоисточник теоремы; полезен для исторически точной формулировки и указания на точность порога.

2. Combinatorics on Words. Классическая монография по комбинаторике на словах; покрывает основной аппарат теории периодов, бордеров, примитивности и связанных результатов.

3. Applied Combinatorics on Words, особенно глава Algorithms on Words. Удобный источник по overlap, border, линейному вычислению бордер-массива и алгоритмической стороне теории слов.

4. 125 Problems in Text Algorithms, глава The Very Basics of Stringology. Очень компактный и удобный для задач источник: периодичность, соответствие «бордер–период», weak periodicity lemma, commutation lemma, primitivity lemma.

5. Algebraic Combinatorics on Words, глава Periodicity. Официальная страница главы прямо указывает, что в ней содержится доказательство теоремы Файна–Вильфа и обобщение на три периода.

6. M. G. Castelli, F. Mignosi, A. Restivo, Fine and Wilf’s theorem for three periods and a generalization of Sturmian words. Официальная страница статьи на ScienceDirect; стандартный источник по обобщению на три периода.

7. J. Justin, On a paper by Castelli, Mignosi, Restivo. Официальная публикация на Numdam; расширяет картину от трёх периодов к произвольному числу периодов.

8. S. Constantinescu, L. Ilie, Generalised Fine and Wilf’s theorem for arbitrary number of periods. Официальная статья на ScienceDirect; один из стандартных источников по общей версии теоремы.

9. Jeffrey Shallit, Fifty Years of Fine and Wilf. Доступный обзорно-исторический материал: эквивалентные формулировки, экстремальные примеры и связь с алгоритмами строк. Полезен как обзор после освоения базовой теории.

10. Русскоязычное дополнительное чтение: А. М. Шур, Ю. В. Гамзова, Частичные слова и свойство Файна–Вильфа на Math-Net.Ru. Это уже не базовая форма теоремы, а её вариант для частичных слов; полезно для расширения темы после освоения классического случая.