Викиконспекты - Вклад участника [ru]

Период и бордер, их связь

2012-05-07T15:13:32Z

178.178.24.167:

==Связь периода и бордера==
{{Теорема
|statement= Если у строки длины <tex>n</tex> есть [[Основные определения, связанные со строками#Отношения между строками|бордер]] длины <tex>k</tex>, то у нее есть [[Основные определения, связанные со строками#Отношения между строками|период]] длины <tex>n - k</tex>.
|proof=
Пусть дана строка <tex>\alpha</tex>.<br/>
Напишем формально определения бордера длины <tex>k</tex> строки <tex>\alpha</tex>:<br/>
<ul><tex>\forall i = 1 \ldots k</tex>, <tex>\alpha [i] = \alpha[i + (n - k)]</tex>.<br/></ul>
Сделаем замену <tex>x = n - k</tex>:<br/>
<ul><tex>\forall i = 1 \ldots n - x</tex>, <tex>\alpha [i] = \alpha[i + x]</tex>.</ul>
Получили определение периода длины <tex>x</tex>. Но <tex>x = n - k</tex>, значит у строки <tex>\alpha</tex> есть период длины <tex>n - k</tex>.
}}

==Свойства периода==
{{Теорема
|statement= Если у строки есть [[Основные определения, связанные со строками#Отношения между строками|период]] длины <tex>k</tex>, то у нее есть период длины <tex>kx</tex>, где <tex> x \in N</tex>.
|proof=
Пусть длина строки равна <tex>n</tex>, сама строка {{---}} <tex>\alpha</tex>.<br/>
Доказательство будем вести по индукции по числу <tex>x</tex>.<br/>
<ol>
<li>Для <tex> x = 1 </tex> утверждение очевидно.</li>
<li>Пусть верно для <tex>x \leqslant m</tex>.</li>
<li>Докажем, что верно для <tex>x = m + 1</tex>.<br/>
Из определения периода имеем, что<br/>
<ul><tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + k]</tex>,</ul>
а из предположения индукции, что<br/>
<ul><tex>\forall i = 1 \ldots n - km</tex>, <tex>\alpha [i] = \alpha[i + mk]</tex></ul>
Значит получаем, что<br/>
<ul><tex>\forall i = 1 \ldots n - km - k</tex>, <tex>\alpha [i] = \alpha [i + mk] = \alpha[i + mk + k]</tex>,</ul>
следовательно<br/>
<ul>для <tex>\forall i = 1 \ldots n - k(m + 1)</tex>, <tex>\alpha [i] = \alpha[i + k(m + 1)]</tex>.</ul>
Значит у строки есть период длины <tex>k(m + 1)</tex>.<br/></li>
</ol>
Утверждение доказано.
}}

{{Теорема
|statement= Если у строки есть периоды длины <tex>p</tex> и <tex>q</tex>, то НОД<tex>(p, q)</tex> также является периодом этой строки.
|proof=
Для удобства доказательства допишем перед строкой её копию и будем нумеровать символы новой строки не с <tex>1</tex> до <tex>2n</tex>, а с <tex>-n + 1</tex> до <tex>n</tex>. Назовём полученную строку <tex>\alpha</tex>.<br/>
Доказательство будем вести по индукции по парам <tex>(p, q)</tex>, где <tex> p \geqslant q </tex>, а <tex>(p, q) + 1 = \begin{cases} (p, q + 1), & q < p;\\
(p + 1, 1), & q = p.\end{cases}</tex><br/>
<ol>
<li>Для <tex> (1, 1) </tex> утверждение очевидно.</li>
<li>Пусть верно для всех пар меньших <tex>(p, q)</tex>.</li>
<li>Докажем, что верно для <tex>(p, q)</tex>.<br/>
Из определения периода:<br/>
<ul><tex>\forall i = -n + 1 \ldots n - p</tex>, <tex>\alpha [i] = \alpha[i + p] = \alpha[i + q]</tex>.</ul>
Значит <ul><tex>\forall i = 1 - q \ldots n - p</tex>, <tex>\alpha [i + q] = \alpha[i + p]</tex></ul>
Сделаем замену <tex>j = i + q</tex> и получим, что<br/>
<ul><tex>\forall j = 1 \ldots n - (p - q)</tex>, <tex>\alpha [j] = \alpha[j + (p - q)]</tex></ul>
Получили новый период длины <tex>p - q</tex>. Из предположения известно, что НОД<tex>(p - q, q)</tex> {{---}} период строки, но НОД<tex>(p - q, q)</tex><tex>=</tex>НОД<tex>(p, q)</tex>.</li>
</ol>
Следовательно утверждение доказано.
}}

== См. также ==
[[Основные определения, связанные со строками]]

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Решение RMQ с помощью разреженной таблицы

2012-05-07T12:08:23Z

178.178.24.167: /* Применение к задаче RMQ */

'''Разреженная таблица''' (англ. ''sparse table'') позволяет решать задачу online static RMQ за <tex>O(1)</tex> на запрос, с предподсчётом за <tex>O(N \log N)</tex> и использованием <tex>O(N \log N)</tex> памяти.
== Постановка задачи RMQ ==
Дан массив <tex>A[1..N]</tex> целых чисел. Поступают запросы вида <tex>(l, r)</tex>: требуется найти минимум среди элементов <tex>A[l], A[l + 1], \dots, A[r] </tex>.

== Разреженная таблица ==
Разреженная таблица — двумерная структура данных <tex>ST[i, j]</tex>, для которой выполнено следующее:

<tex>ST[i][j]=\min\left(A[i], A[i+1], ..., A[i+2^{j}-1]\right),\quad j \in [0 .. \log N]</tex>.

Иначе говоря, в этой таблице хранятся минимумы на всех отрезках, длины которых равны степеням двойки. Объём памяти, занимаемый таблицей, равен <tex>O(N \log N)</tex>, и заполненными являются только те элементы, для которых <tex>i+2^j \le N </tex>.

Простой метод построения таблицы заключён в следующем реккурентном соотношении:

<tex> ST[i][j] =
\left\{
\begin{array}{rcl}
\min\left(ST[i][j-1], ST[i+2^{j-1}][j-1]\right), j > 0 \\
A[i], j = 0. \\
\end{array}
\right.
</tex>
=== Идемпотентность ===
Такая простота достигается за счет идемпотентности операции минимум: <tex>\min(a, a)=a</tex>. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков.
<wikitex>
Пусть $\circ$ — произвольная бинарная операция, которая удовлетворяет свойствам:
* ассоциативности: $a \circ (b \circ c) = (a \circ b) \circ c $;
* коммутативности: $a \circ b = b \circ a$;
* идемпотентности: $a \circ a = a $.

{{Утверждение
|statement=
$a_l \circ a_{l+1} \circ \dots \circ a_r = (a_l \circ a_{l+1} \circ \dots \circ a_k) \circ (a_{r - k} \circ a_{r - k + 1} \circ \dots \circ a_r)$, где $l \leqslant k \leqslant r$.
|proof=
Отрезок $(a_{r-k}, a_k)$ содержится в обои операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем располагать элементы в любом порядке, по ассоциативности мы можем выполнять операции в произвольном порядке, поэтому повторяющие в правой части элементы мы можем расположить рядом друг с другом и затем по идемпотентности один из них убрать. Переставляя оставшиеся элементы в правой затем легко получаем выражение в левой части.
}}
</wikitex>

== Применение к задаче RMQ ==
[[Файл:SparseTableRMQ.png|right|Решение задачи RMQ на разреженной таблице]]
<div> Предпосчитаем для длины отрезка <tex>l</tex> величину <tex>k =\lfloor \log_2l \rfloor</tex>. Это можно сделать за <tex>O(N\log N)</tex> введением функции <tex>fl[l] = k</tex>, для которой верно <tex>fl[1] = 0, fl[x] = fl[\lfloor \frac{x}{2}\rfloor] + 1</tex>.

Пусть теперь дан запрос <tex>(l, r)</tex>. Заметим, что <tex>\min(A[l], A[l+1], ..., A[r]) = \min\left(ST[l][k], ST[r-2^k+1][j]\right)</tex>, где <tex>k = \max \{j| 2^j \le r - l + 1\}</tex>, т.е. логарифм длины запрашиваемого отрезка, округленный вниз. Но эту величину мы уже предпосчитали, поэтому запрос выполняется за <tex>O (1)</tex>.

Стоит отметить, что этот метод работает не только с операцией минимум, но и с любой идемпотентной, ассоциативной и коммутативной операцией, так как отрезки <tex>(l, 2^k)</tex> и <tex>(r - 2^k, r)</tex>, на которых мы считаем ответ, есть те самые из доказанного утверждения. Таким образом мы получаем целый класс задач, решаемых разреженной таблицей.
<div style="clear:both"></div>

== См. также ==
* [[Сведение задачи LCA к задаче RMQ | Сведение задачи LCA к задаче RMQ]]
* [[Алгоритм Фарака-Колтона и Бендера | Алгоритм Фарака-Колтона и Бендера]]
* [[Сведение задачи RMQ к задаче LCA | Сведение задачи RMQ к задаче LCA]]

== Источники ==
* ''Bender, M.A., Farach-Colton, M. et al.'' — '''Lowest common ancestors in trees and directed acyclic graphs'''. — J. Algorithms 57(2) (2005) — с. 75–94.

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]

Решение RMQ с помощью разреженной таблицы

2012-05-07T11:57:13Z

178.178.24.167: /* Разреженная таблица */

'''Разреженная таблица''' (англ. ''sparse table'') позволяет решать задачу online static RMQ за <tex>O(1)</tex> на запрос, с предподсчётом за <tex>O(N \log N)</tex> и использованием <tex>O(N \log N)</tex> памяти.
== Постановка задачи RMQ ==
Дан массив <tex>A[1..N]</tex> целых чисел. Поступают запросы вида <tex>(l, r)</tex>: требуется найти минимум среди элементов <tex>A[l], A[l + 1], \dots, A[r] </tex>.

== Разреженная таблица ==
Разреженная таблица — двумерная структура данных <tex>ST[i, j]</tex>, для которой выполнено следующее:

<tex>ST[i][j]=\min\left(A[i], A[i+1], ..., A[i+2^{j}-1]\right),\quad j \in [0 .. \log N]</tex>.

Иначе говоря, в этой таблице хранятся минимумы на всех отрезках, длины которых равны степеням двойки. Объём памяти, занимаемый таблицей, равен <tex>O(N \log N)</tex>, и заполненными являются только те элементы, для которых <tex>i+2^j \le N </tex>.

Простой метод построения таблицы заключён в следующем реккурентном соотношении:

<tex> ST[i][j] =
\left\{
\begin{array}{rcl}
\min\left(ST[i][j-1], ST[i+2^{j-1}][j-1]\right), j > 0 \\
A[i], j = 0. \\
\end{array}
\right.
</tex>
=== Идемпотентность ===
Такая простота достигается за счет идемпотентности операции минимум: <tex>\min(a, a)=a</tex>. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков.
<wikitex>
Пусть $\circ$ — произвольная бинарная операция, которая удовлетворяет свойствам:
* ассоциативности: $a \circ (b \circ c) = (a \circ b) \circ c $;
* коммутативности: $a \circ b = b \circ a$;
* идемпотентности: $a \circ a = a $.

{{Утверждение
|statement=
$a_l \circ a_{l+1} \circ \dots \circ a_r = (a_l \circ a_{l+1} \circ \dots \circ a_k) \circ (a_{r - k} \circ a_{r - k + 1} \circ \dots \circ a_r)$, где $l \leqslant k \leqslant r$.
|proof=
Отрезок $(a_{r-k}, a_k)$ содержится в обои операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем располагать элементы в любом порядке, по ассоциативности мы можем выполнять операции в произвольном порядке, поэтому повторяющие в правой части элементы мы можем расположить рядом друг с другом и затем по идемпотентности один из них убрать. Переставляя оставшиеся элементы в правой затем легко получаем выражение в левой части.
}}
</wikitex>

== Применение к задаче RMQ ==
[[Файл:SparseTableRMQ.png|right|Решение задачи RMQ на разреженной таблице]]
<div> Предпосчитаем длину отрезка <tex>k</tex>. Это можно сделать за <tex>O(N\log N)</tex> введением функции <tex>fl[l] = k</tex>, для которой верно <tex>fl[1] = 0, fl[x] = fl[\lfloor \frac{x}{2}\rfloor] + 1</tex>.

Пусть теперь дан запрос <tex>(l, r)</tex>. Заметим, что <tex>\min(A[l], A[l+1], ..., A[r]) = \min\left(ST[l][k], ST[r-2^k+1][j]\right)</tex>, где <tex>k = \max \{j| 2^j \le r - l + 1\}</tex>, т.е. логарифм длины запрашиваемого отрезка, округленный вниз. Но эту величину мы уже предпосчитали, поэтому запрос выполняется за <tex>O (1)</tex>.

Стоит отметить, что этот метод работает не только с операцией минимум, но и с любой идемпотентной, ассоциативной и коммутативной операцией, так как отрезки <tex>(l, 2^k)</tex> и <tex>(r - 2^k, r)</tex>, на которых мы считаем ответ, есть те самые из доказанного утверждения. Таким образом мы получаем целый класс задач, решаемых разреженной таблицей.
<div style="clear:both"></div>

== См. также ==
* [[Сведение задачи LCA к задаче RMQ | Сведение задачи LCA к задаче RMQ]]
* [[Алгоритм Фарака-Колтона и Бендера | Алгоритм Фарака-Колтона и Бендера]]
* [[Сведение задачи RMQ к задаче LCA | Сведение задачи RMQ к задаче LCA]]

== Источники ==
* ''Bender, M.A., Farach-Colton, M. et al.'' — '''Lowest common ancestors in trees and directed acyclic graphs'''. — J. Algorithms 57(2) (2005) — с. 75–94.

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]

Решение RMQ с помощью разреженной таблицы

2012-05-07T11:38:25Z

178.178.24.167: /* Постановка задачи RMQ */

'''Разреженная таблица''' (англ. ''sparse table'') позволяет решать задачу online static RMQ за <tex>O(1)</tex> на запрос, с предподсчётом за <tex>O(N \log N)</tex> и использованием <tex>O(N \log N)</tex> памяти.
== Постановка задачи RMQ ==
Дан массив <tex>A[1..N]</tex> целых чисел. Поступают запросы вида <tex>(l, r)</tex>: требуется найти минимум среди элементов <tex>A[l], A[l + 1], \dots, A[r] </tex>.

== Разреженная таблица ==
Разреженная таблица — двумерная структура данных <tex>ST[i, j]</tex>, для которой выполнено следующее: <tex>ST[i][j]=\min\left(A[i], A[i+1], ..., A[i+2^{j}-1]\right),\quad j \in [0 .. \log N]</tex>. Иначе говоря, в этой таблице хранятся минимумы на всех отрезках, длины которых равны степеням двойки. Объём, занимаемый таблицей, равен <tex>O(N \log N)</tex>, и заполненными являются только те элементы, для которых <tex>i+2^j \le N </tex>.

Простой метод построения таблицы заключён в следующем реккурентном соотношении:

<tex> ST[i][j] =
\left\{
\begin{array}{rcl}
\min\left(ST[i][j-1], ST[i+2^{j-1}][j-1]\right), j > 0 \\
A[i], j = 0 \\
\end{array}
\right.
</tex> .
=== Идемпотентность ===
Такая простота достигается за счет идемпотентности операции минимум: <tex>\min(a, a)=a</tex>. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков.
<wikitex>
Пусть $\circ$ — произвольная бинарная операция, которая удовлетворяет свойствам:
* ассоциативности: $a \circ (b \circ c) = (a \circ b) \circ c $;
* коммутативности: $a \circ b = b \circ a$;
* идемпотентности: $a \circ a = a $.

{{Утверждение
|statement=
$a_l \circ a_{l+1} \circ \dots \circ a_r = (a_l \circ a_{l+1} \circ \dots \circ a_k) \circ (a_{r - k} \circ a_{r - k + 1} \circ \dots \circ a_r)$, где $l \leqslant k \leqslant r; \frac{l}{2} \leqslant k$.
|proof=
Отрезок $(a_{r-k}, a_k)$ содержится в обои операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем расположить повторяющиеся элементы друг с другом. По ассоциотивности мы можем расставлять скобки как угодно, в том числе, обособляя эти самые повторы. А за счет идемпотентности мы от них избавляемся. В итоге, получаем выражение в левой части равенства.
}}
</wikitex>

== Применение к задаче RMQ ==
[[Файл:SparseTableRMQ.png|right|Решение задачи RMQ на разреженной таблице]]
<div> Предпосчитаем длину отрезка <tex>k</tex>. Это можно сделать за <tex>O(N\log N)</tex> введением функции <tex>fl[l] = k</tex>, для которой верно <tex>fl[1] = 0, fl[x] = fl[\lfloor \frac{x}{2}\rfloor] + 1</tex>.

Пусть теперь дан запрос <tex>(l, r)</tex>. Заметим, что <tex>\min(A[l], A[l+1], ..., A[r]) = \min\left(ST[l][k], ST[r-2^k+1][j]\right)</tex>, где <tex>k = \max \{j| 2^j \le r - l + 1\}</tex>, т.е. логарифм длины запрашиваемого отрезка, округленный вниз. Но эту величину мы уже предпосчитали, поэтому запрос выполняется за <tex>O (1)</tex>.

Стоит отметить, что этот метод работает не только с операцией минимум, но и с любой идемпотентной, ассоциативной и коммутативной операцией, так как отрезки <tex>(l, 2^k)</tex> и <tex>(r - 2^k, r)</tex>, на которых мы считаем ответ, есть те самые из доказанного утверждения. Таким образом мы получаем целый класс задач, решаемых разреженной таблицей.
<div style="clear:both"></div>

== См. также ==
* [[Сведение задачи LCA к задаче RMQ | Сведение задачи LCA к задаче RMQ]]
* [[Алгоритм Фарака-Колтона и Бендера | Алгоритм Фарака-Колтона и Бендера]]
* [[Сведение задачи RMQ к задаче LCA | Сведение задачи RMQ к задаче LCA]]

== Источники ==
* ''Bender, M.A., Farach-Colton, M. et al.'' — '''Lowest common ancestors in trees and directed acyclic graphs'''. — J. Algorithms 57(2) (2005) — с. 75–94.

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]

Решение RMQ с помощью разреженной таблицы

2012-05-07T11:37:38Z

178.178.24.167: /* Постановка задачи RMQ */

'''Разреженная таблица''' (англ. ''sparse table'') позволяет решать задачу online static RMQ за <tex>O(1)</tex> на запрос, с предподсчётом за <tex>O(N \log N)</tex> и использованием <tex>O(N \log N)</tex> памяти.
== Постановка задачи RMQ ==
Дан массив <tex>A[1..N]</tex> целых чисел. Поступают запросы вида <tex>(l, r)</tex>: найти минимум в подмассиве <tex>A[l], A[l + 1], \dots, A[r] </tex>.

== Разреженная таблица ==
Разреженная таблица — двумерная структура данных <tex>ST[i, j]</tex>, для которой выполнено следующее: <tex>ST[i][j]=\min\left(A[i], A[i+1], ..., A[i+2^{j}-1]\right),\quad j \in [0 .. \log N]</tex>. Иначе говоря, в этой таблице хранятся минимумы на всех отрезках, длины которых равны степеням двойки. Объём, занимаемый таблицей, равен <tex>O(N \log N)</tex>, и заполненными являются только те элементы, для которых <tex>i+2^j \le N </tex>.

Простой метод построения таблицы заключён в следующем реккурентном соотношении:

<tex> ST[i][j] =
\left\{
\begin{array}{rcl}
\min\left(ST[i][j-1], ST[i+2^{j-1}][j-1]\right), j > 0 \\
A[i], j = 0 \\
\end{array}
\right.
</tex> .
=== Идемпотентность ===
Такая простота достигается за счет идемпотентности операции минимум: <tex>\min(a, a)=a</tex>. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков.
<wikitex>
Пусть $\circ$ — произвольная бинарная операция, которая удовлетворяет свойствам:
* ассоциативности: $a \circ (b \circ c) = (a \circ b) \circ c $;
* коммутативности: $a \circ b = b \circ a$;
* идемпотентности: $a \circ a = a $.

{{Утверждение
|statement=
$a_l \circ a_{l+1} \circ \dots \circ a_r = (a_l \circ a_{l+1} \circ \dots \circ a_k) \circ (a_{r - k} \circ a_{r - k + 1} \circ \dots \circ a_r)$, где $l \leqslant k \leqslant r; \frac{l}{2} \leqslant k$.
|proof=
Отрезок $(a_{r-k}, a_k)$ содержится в обои операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем расположить повторяющиеся элементы друг с другом. По ассоциотивности мы можем расставлять скобки как угодно, в том числе, обособляя эти самые повторы. А за счет идемпотентности мы от них избавляемся. В итоге, получаем выражение в левой части равенства.
}}
</wikitex>

== Применение к задаче RMQ ==
[[Файл:SparseTableRMQ.png|right|Решение задачи RMQ на разреженной таблице]]
<div> Предпосчитаем длину отрезка <tex>k</tex>. Это можно сделать за <tex>O(N\log N)</tex> введением функции <tex>fl[l] = k</tex>, для которой верно <tex>fl[1] = 0, fl[x] = fl[\lfloor \frac{x}{2}\rfloor] + 1</tex>.

Пусть теперь дан запрос <tex>(l, r)</tex>. Заметим, что <tex>\min(A[l], A[l+1], ..., A[r]) = \min\left(ST[l][k], ST[r-2^k+1][j]\right)</tex>, где <tex>k = \max \{j| 2^j \le r - l + 1\}</tex>, т.е. логарифм длины запрашиваемого отрезка, округленный вниз. Но эту величину мы уже предпосчитали, поэтому запрос выполняется за <tex>O (1)</tex>.

Стоит отметить, что этот метод работает не только с операцией минимум, но и с любой идемпотентной, ассоциативной и коммутативной операцией, так как отрезки <tex>(l, 2^k)</tex> и <tex>(r - 2^k, r)</tex>, на которых мы считаем ответ, есть те самые из доказанного утверждения. Таким образом мы получаем целый класс задач, решаемых разреженной таблицей.
<div style="clear:both"></div>

== См. также ==
* [[Сведение задачи LCA к задаче RMQ | Сведение задачи LCA к задаче RMQ]]
* [[Алгоритм Фарака-Колтона и Бендера | Алгоритм Фарака-Колтона и Бендера]]
* [[Сведение задачи RMQ к задаче LCA | Сведение задачи RMQ к задаче LCA]]

== Источники ==
* ''Bender, M.A., Farach-Colton, M. et al.'' — '''Lowest common ancestors in trees and directed acyclic graphs'''. — J. Algorithms 57(2) (2005) — с. 75–94.

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]

Слово Туэ-Морса

2012-05-07T10:15:59Z

178.178.24.167:

{{Определение
|definition=
Определим последовательность строк <tex>T_n</tex> над двухбуквенным алфавитом <tex>\{a, b\}</tex> следующим образом: <tex>T_n = t_0 t_1 \dots t_{2^n-1}</tex>, где:
* <tex>t_i = a</tex>, если двоичная запись числа <tex>i</tex> содержит чётное число единиц
* <tex>t_i = b</tex>, иначе.

Строки этой последовательности называются '''строками Туэ-Морса'''.
}}

== Примеры ==

Приведём первые пять строк Туэ-Морса:
* <tex>T_0 = a</tex>
* <tex>T_1 = ab</tex>
* <tex>T_2 = abba</tex>
* <tex>T_3 = abbabaab</tex>
* <tex>T_4 = abbabaabbaababba</tex>

== Свойства и эквивалентные определения ==

Как видно из определения, символ на <tex>i</tex>-ой позиции не зависит от номера строки. Так как длина строк возрастает, каждая строка является собственным префиксом следующей, поэтому можно рассматривать получение следующей строки как приписывание к текущей строке некоторой другой строки.

{{Теорема
|statement=
Пусть <tex>\varphi</tex> — морфизм, инвертирующий символы:
<tex>\varphi(x) = \left\{ \begin{array}{rl}
b, & x = a \\
a, & x = b, \\
\end{array} \right.</tex>

тогда для строк Туэ-Морса верно следующее соотношение: <tex>T_{n + 1} = T_n \varphi(T_n)</tex>
|proof=
Заметим, что соответсвующие индексы символов при приписывании новой строки к строке <tex>T_n</tex> получаются добавлением к индексам <tex>i = 0, 1, \dots, 2^n - 1</tex> числа <tex>2^n</tex>. Количество единиц в двоичной записи числа <tex>i + 2^n</tex> (<tex>i < 2^n</tex>) ровно на один больше, чем в двоичной записи числа <tex>i</tex>. Поэтому приписываемая строка есть ни что иное, как исходная строка с инвертированными символами.
}}

Данная теорема позволяет определять последовательность строк Туэ-Морса следующим образом: <tex>T_0 = a</tex>, <tex>T_{n + 1} = T_n \varphi(T_n)</tex>.

Часто рассматривают предельный случай — бесконечную строку Туэ-Морса, любой символ которой можно получить из обычной строки Туэ-Морса с достаточно большим номером. Бесконечную строку также можно задать с помощью правил ассоциативного исчисления, клеточного автомата, рекурсивных соотношений.

== См. также ==
[[Слово Фибоначчи]]

== Ссылки ==
* [http://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence Wikipedia — Thue-Morse sequence]
* [http://mathworld.wolfram.com/Thue-MorseSequence.html Wolfram Mathworld — Thue-Morse sequence]

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Слово Туэ-Морса

2012-05-07T10:07:09Z

178.178.24.167: /* Свойства и эквивалентные определения */

{{Определение
|definition=
Определим последовательность строк <tex>T_n</tex> над двухбуквенным алфавитом <tex>\{a, b\}</tex> следующим образом: <tex>T_n = t_0 t_1 \dots t_{2^n-1}</tex>, где:
* <tex>t_i = a</tex>, если двоичная запись числа <tex>i</tex> содержит чётное число единиц
* <tex>t_i = b</tex>, иначе.

Строки этой последовательности называются '''строками Туэ-Морса'''.
}}

== Примеры ==

Приведём первые пять строк Туэ-Морса:
* <tex>T_0 = a</tex>
* <tex>T_1 = ab</tex>
* <tex>T_2 = abba</tex>
* <tex>T_3 = abbabaab</tex>
* <tex>T_4 = abbabaabbaababba</tex>

== Свойства и эквивалентные определения ==

Как видно из определения, символ на <tex>i</tex>-ой позиции не зависит от номера строки. Так как длина строк возрастает, каждая строка является собственным префиксом следующей, поэтому можно рассматривать получение следующей строки как приписывание к текущей строке некоторой другой строки.

{{Теорема
|statement=
Пусть <tex>\varphi</tex> — морфизм, инвертирующий символы:
<tex>\varphi(x) = \left\{ \begin{array}{rl}
b, & x = a \\
a, & x = b, \\
\end{array} \right.</tex>

тогда для строк Туэ-Морса верно следующее соотношение: <tex>T_{n + 1} = T_n \varphi(T_n)</tex>
|proof=
Заметим, что соответсвующие индексы символов при приписывании новой строки к строке <tex>T_n</tex> получаются добавлением к индексам <tex>i = 0, 1, \dots, 2^n - 1</tex> числа <tex>2^n</tex>. Количество единиц в двоичной записи числа <tex>i + 2^n</tex> (<tex>i < 2^n</tex>) ровно на один больше, чем в двоичной записи числа <tex>i</tex>. Поэтому приписываемая строка есть ни что иное, как исходная строка с инвертированными символами.
}}

Данная теорема позволяет определять последовательность строк Туэ-Морса следующим образом: <tex>T_0 = a</tex>, <tex>T_{n + 1} = T_n \varphi(T_n)</tex>.

Часто рассматривают предельный случай — бесконечную строку Туэ-Морса, любой символ которой можно получить из обычной строки Туэ-Морса с достаточно большим номером. Бесконечную строку также можно задать с помощью правил ассоциативного исчисления, клеточного автомата, рекурсивных соотношений.

== Ссылки ==
* [http://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence Wikipedia — Thue-Morse sequence]
* [http://mathworld.wolfram.com/Thue-MorseSequence.html Wolfram Mathworld — Thue-Morse sequence]

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Слово Туэ-Морса

2012-05-07T10:02:49Z

178.178.24.167: /* Свойства и эквивалентные определения */

{{Определение
|definition=
Определим последовательность строк <tex>T_n</tex> над двухбуквенным алфавитом <tex>\{a, b\}</tex> следующим образом: <tex>T_n = t_0 t_1 \dots t_{2^n-1}</tex>, где:
* <tex>t_i = a</tex>, если двоичная запись числа <tex>i</tex> содержит чётное число единиц
* <tex>t_i = b</tex>, иначе.

Строки этой последовательности называются '''строками Туэ-Морса'''.
}}

== Примеры ==

Приведём первые пять строк Туэ-Морса:
* <tex>T_0 = a</tex>
* <tex>T_1 = ab</tex>
* <tex>T_2 = abba</tex>
* <tex>T_3 = abbabaab</tex>
* <tex>T_4 = abbabaabbaababba</tex>

== Свойства и эквивалентные определения ==

Как видно из определения, символ на <tex>i</tex>-ой позиции не зависит от номера строки. Так как длина строк возрастает, каждая строка является собственным префиксом следующей, поэтому можно рассматривать получение следующей строки как приписывание к текущей строке некоторой другой строки.

{{Теорема
|statement=
Пусть <tex>\varphi</tex> — морфизм, инвертирующий символы:
<tex>\varphi(x) = \left\{ \begin{array}{rl}
b, & x = a \\
a, & x = b, \\
\end{array} \right.</tex>

тогда для строк Туэ-Морса верно следующее соотношение: <tex>T_{n + 1} = T_n \varphi(T_n)</tex>
|proof=
Заметим, что соответсвующие индексы символов при приписывании новой строки к строке <tex>T_n</tex> получаются добавлением к индексам <tex>i = 0, 1, \dots, 2^n - 1</tex> числа <tex>2^n</tex>. Количество единиц в двоичной записи числа <tex>i + 2^n</tex> ровно на один больше, чем в двоичной записи числа <tex>i</tex>. Поэтому приписываемая строка есть ни что иное, как исходная строка с инвертированными символами.
}}

Данная теорема позволяет определять последовательность строк Туэ-Морса следующим образом: <tex>T_0 = a</tex>, <tex>T_{n + 1} = T_n \varphi(T_n)</tex>.

Часто рассматривают предельный случай — бесконечную строку Туэ-Морса, любой символ которой можно получить из обычной строки Туэ-Морса с достаточно большим номером. Бесконечную строку также можно задать с помощью правил ассоциативного исчисления, клеточного автомата, рекурсивных соотношений.

== Ссылки ==
* [http://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence Wikipedia — Thue-Morse sequence]
* [http://mathworld.wolfram.com/Thue-MorseSequence.html Wolfram Mathworld — Thue-Morse sequence]

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Суффиксный бор

2012-05-07T09:25:38Z

178.178.24.167: /* Хранение в памяти */

[[Файл:Suffix_trie.png|thumb|right|Суффиксный бор для строки <tex>abbc</tex>]]
'''Суффиксный бор''' (англ. ''suffix trie'') {{---}} [[бор]], содержащий все суффиксы данной строки.

По определению, в суффиксном боре для строки <tex>s</tex> (где <tex>\lvert s\rvert=n</tex>) содержатся все строки <tex>s[1..n], ..., s[n..n]</tex>. Заметим, что если в суффиксном боре находится строка <tex>s[i..n]</tex>, то все ее префиксы <tex>s[i..j], i \le j \le n</tex> уже содержатся в боре.
==Применение==
Суффиксный бор можно использовать для поиска подстроки в строке <tex>s</tex> (чтобы бор формально содержал все подстроки <tex>s</tex>, нужно пометить все его вершины терминальными, при этом корень будет соответствовать пустой строке <tex>\varepsilon</tex>).
Для поиска подстроки p в суффиксном боре нужно искать совпадения для символов из p вдоль единственного пути в боре до тех пор, пока либо p не исчерпается, либо дальнейшее совпадение будет невозможным. Если p исчерпалось, то подстрока найдена за <tex>O(|p|)</tex>, если дальнейшее совпадение невозможно, то p нет в суффиксном дереве.

==Свойства==
Суффиксный бор для строки <tex>s</tex>:
* Можно использовать для поиска образца <tex>p</tex> в строке <tex>s</tex> за время <tex>O(\lvert p\rvert)</tex>.
* Можно построить за время <tex>O(n^2)</tex>, последовательно добавив все суффиксы <tex>s</tex>.
* Имеет порядка <tex>n^2</tex> вершин.

== Реализация ==
'''struct Trie'''
int [length^2][alphabet] trie
number <tex> \leftarrow 1</tex>

'''Add'''(i, j)
current <tex>\leftarrow</tex> 0
'''for''' (char c <tex>\in</tex> s[i, j])
if (trie[current][c] <tex>\neq </tex> -1)
trie[current][c] <tex> \leftarrow</tex> number
number++;
current <tex>\leftarrow</tex> trie[current][c]

'''Build'''(String s)
'''for'''(int i = 0, i < n, i++)
Add(i, n)

==Оценки использования памяти==
Пусть мы построили суффиксный бор для строки <tex>s \in \Sigma*</tex>, <tex>|s| = n</tex>. Из третьего свойства следует, что если хранить переходы суффиксного бора из каждой вершины как массив размера <tex>|\Sigma|</tex> (по каждому символу — ребенок), то потребуется <tex>O(n^2 |\Sigma|)</tex> памяти.
Однако, заметим, что число ветвлений в боре равно количеству суффиксов, так как каждый лист соответствует единственному суффиксу. Количество суффиксов — <tex>n</tex>, а значит число вершин, из которых ведет больше одного перехода, <tex>O(n)</tex>. Поэтому, если в неветвящихся вершинах хранить только символ перехода и ребенка, то можно получить оценку <tex>O(n^2 + n|\Sigma|)</tex>. Улучшением суффиксного бора, расходующим всего <tex>O( n|\Sigma|)</tex> памяти, является [[сжатое суффиксное дерево]].

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Словарные структуры данных]]