Изменения
Нет описания правки
== Пример построения автокорреляционного многочлена ==
Пусть имеем алфавит <tex>\Sigma = \{0, 1\}</tex>, рассмотрим строку <tex>p=001100</tex>. Будем проверять факт совпадения суффикса и префикса строки <tex>p</tex>, используя следующую таблицу:'''Не очень понятная таблица. Ну, субъективно, не очень помогает понять. Может, переформатировать?'''
{| class="wikitable"
!0
| definition = Пусть <tex>\Sigma</tex> {{---}} данный алфавит, <tex>p</tex> {{---}} данная непустая строка над алфавитом <tex>\Sigma</tex>. Найти производящую функцию множества слов, не содержащих <tex>p</tex> как подстроку.
}}
Пусть <tex>|\Sigma| = m</tex> {{---}} мощность алфавита <tex>\Sigma</tex>, <tex>S</tex> {{---}} множество слов, не содержащих <tex>p</tex> как подстроку, <tex>\alpha \in S</tex> {{---}} произвольное слово из <tex>S</tex>, <tex>T</tex> {{---}} множество слов, содержащих <tex>p</tex> как подстроку только в самом конце. Рассмотрим все слова вида <tex>\alpha \sigma_1, \alpha \sigma_2, \dots, \alpha \sigma_m</tex>, где <tex>\sigma_1, \sigma_2, \dots, \sigma_m</tex> {{---}} все символы алфавита <tex>\Sigma</tex>. Так как слово <tex>\alpha</tex> не содержало подстроку <tex>p</tex>, то после добавления символа <tex>\sigma_i</tex> новая строка либо так же не содержит <tex>p</tex> как подстроку, и, следовательно, <tex>\alpha\sigma_i \in S</tex>, либо содержит, но только в самом конце, и тогда <tex>\alpha\sigma_i \in T</tex>. Очевидно также, что от удаления последнего символа у слова из <tex>T</tex> всегда получается слово из <tex>S</tex>, то есть, путём добавления ко всем <tex>\alpha \in S</tex> символа <tex>\sigma_i \in \Sigma, i=\overline{1,m},</tex> мы получим все непустые слова из <tex>T</tex> и <tex>S</tex>. В контексте комбинаторных объектов это выражается в равенстве <tex> \{\epsilon\} + S \times \Sigma = \Sigma + T</tex>, где <tex>\epsilon </tex> {{---}} комбинаторный объект веса 0, соответствующий пустой строке.'''Тут справа не S + T?'''
Рассмотрим теперь слова вида <tex>\alpha p</tex>. После добавления к слову <tex>\alpha</tex> строки <tex>p</tex> мы точно получим все строки из <tex>T</tex>, но, кроме них, могут также получиться строки, имеющие первое вхождение <tex>p</tex> не в самом конце, следовательно, нельзя утверждать, что <tex>\alpha p</tex> всегда принадлежит <tex>T</tex>. Несложно заметить, что <tex> \alpha p \notin T </tex> тогда и только тогда, когда <tex> \alpha p </tex> имеет 2 перекрывающихся вхождения строки <tex>p</tex>. Для того чтобы <tex> \alpha p </tex> имело 2 перекрывающихся вхождения строки <tex>p</tex> необходимо, чтобы <tex>p</tex> имела какой-нибудь суффикс, совпадающий с каким-нибудь префиксом, иначе говоря, чтобы <tex>p</tex> имело автокорреляционный многочлен <tex>C(z) \ne 1</tex>. В результате выходит, что при добавлении ко всем <tex>\alpha \in S</tex> строки <tex>p</tex> получим все строки из <tex>T</tex>, а также все строки, имеющие 2 перекрывающиеся вхождения строки <tex>p</tex>, иными словами, все строки вида <tex>\gamma p_0p_1 \dots p_i \dots p_{k-1} p_{k-i} p_{k-i+1} \dots p_{k-1}</tex> (или, что то же, <tex>\gamma p_0p_1 \dots p_{i-1} p_1 p_2 \dots p_{k-1}</tex>), где <tex>\gamma</tex> {{---}} некоторый префикс <tex>\alpha</tex>, <tex>i \in \overline{1, k-1}</tex>, {{---}} номер некоторого ненулевого коэффициента автокорреляционного многочлена <tex>C(z)</tex> строки <tex>p</tex>. Нетрудно заметить, что <tex>\gamma p_0p_1 \dots p_i \dots p_{k-1} p_{k-i} p_{k-i+1} \dots p_{k-1}</tex> можно представить как некую строку <tex>t \in T</tex> с приписанным в конец суффиксом строки <tex>p</tex> длины <tex>i</tex>. В контексте комбинаторных объектов суффикс строки <tex>p</tex> длины <tex>i</tex> является комбинаторным объектом веса <tex>i</tex>, а его производящей функцией является <tex>z^i</tex>, то есть, по сути, это слагаемое автокорреляционного многочлена <tex>C(z)</tex>. Тогда получаем следующее равенство: <tex>S \times \{p\} = T + \dots + T \times \{p_{k-i} p_{k-i+1} \dots p_{k-1}\} + \dots = T \times C</tex>, где <tex>C</tex> {{---}} комбинаторный класс, соответствующий автокорреляционному многочлену <tex>C(z)</tex>.
:<tex>
\begin{cases}
\{\epsilon\} + S \times \Sigma = \Sigma + T '''и тут тоже S'''\\
S \times \{p\} = T \times C \\
\end{cases}
