Автокорреляционный многочлен

Определение:

Автокорреляционный многочлен (англ. autocorrelation polynomial) для строки [math]p[/math] длины [math]k[/math] — это многочлен вида [math]C(z)=\sum\limits_{i=0}^{k-1} c_i z^i[/math], причем [math]c_i = 1[/math], если префикс строки [math]p[/math] длины [math]k-i[/math] совпадает с суффиксом строки [math]p[/math] длины [math]k-i[/math], иначе [math]c_i = 0[/math]: [math]c_i(x) = \begin{cases} 1,\ \ p_0 \dots p_{k-i-1} = p_i \dots p_{k-1} \\ 0,\ \ p_0 \dots p_{k-i-1} \ne p_i \dots p_{k-1} \\ \end{cases} [/math]

Пример построения автокорреляционного многочлена

Пусть имеем алфавит [math]\Sigma = \{0, 1\}[/math], рассмотрим строку [math]p=001100[/math]. Будем проверять факт совпадения суффикса и префикса строки [math]p[/math], используя следующую таблицу:

0	0	1	1	0	0						c0 = 1
0	0	1	1	0	0
0	0	1	1	0	0						c1 = 0
	0	0	1	1	0	0
0	0	1	1	0	0						c2 = 0
		0	0	1	1	0	0
0	0	1	1	0	0						c3 = 0
			0	0	1	1	0	0
0	0	1	1	0	0						c4 = 1
				0	0	1	1	0	0
0	0	1	1	0	0						c5 = 1
					0	0	1	1	0	0

В итоге автокорреляционный многочлен строки [math]p=001100[/math] равен [math]C(z) = 1 + z^4 + z^5[/math].

Несложно заметить, что [math]c_0[/math] всегда равняется [math]1[/math], ибо префикс и суффикс длины [math]k[/math] являются исходной строкой и, следовательно, всегда совпадают. [math]c_{k-1}[/math] равняется [math]1[/math] только в том случае, если первый и последний символы строки совпадают.

Примеры решений задач с использованием автокорреляционного многочлена

Задача:

Пусть [math]\Sigma[/math] — данный алфавит, [math]p[/math] — данная непустая строка над алфавитом [math]\Sigma[/math]. Найти производящую функцию множества слов, не содержащих [math]p[/math] как подстроку.

Пусть [math]|\Sigma| = m[/math] — мощность алфавита [math]\Sigma[/math], [math]S[/math] — множество слов, не содержащих [math]p[/math] как подстроку, [math]\alpha \in S[/math] — произвольное слово из [math]S[/math], [math]T[/math] — множество слов, содержащих [math]p[/math] как подстроку только в самом конце. Рассмотрим все слова вида [math]\alpha \sigma_1, \alpha \sigma_2, \dots, \alpha \sigma_m[/math], где [math]\sigma_1, \sigma_2, \dots, \sigma_m[/math] — все символы алфавита [math]\Sigma[/math]. Так как слово [math]\alpha[/math] не содержало подстроку [math]p[/math], то после добавления символа [math]\sigma_i[/math] новая строка либо так же не содержит [math]p[/math] как подстроку, и, следовательно, [math]\alpha\sigma_i \in S[/math], либо содержит, но только в самом конце, и тогда [math]\alpha\sigma_i \in T[/math]. Очевидно также, что от удаления последнего символа у слова из [math]T[/math] всегда получается слово из [math]S[/math], то есть, путём добавления ко всем [math]\alpha \in S[/math] символа [math]\sigma_i \in \Sigma, i=\overline{1,m},[/math] мы получим все непустые слова из [math]T[/math] и [math]S[/math]. В контексте комбинаторных объектов это выражается в равенстве [math] \{\epsilon\} + S \times \Sigma = S + T[/math], где [math]\epsilon [/math] — комбинаторный объект веса 0, соответствующий пустой строке.

Рассмотрим теперь слова вида [math]\alpha p[/math]. После добавления к слову [math]\alpha[/math] строки [math]p[/math] мы точно получим все строки из [math]T[/math], но, кроме них, могут также получиться строки, имеющие первое вхождение [math]p[/math] не в самом конце, следовательно, нельзя утверждать, что [math]\alpha p[/math] всегда принадлежит [math]T[/math]. Несложно заметить, что [math] \alpha p \notin T [/math] тогда и только тогда, когда [math] \alpha p [/math] имеет 2 перекрывающихся вхождения строки [math]p[/math]. Для того чтобы [math] \alpha p [/math] имело 2 перекрывающихся вхождения строки [math]p[/math] необходимо, чтобы [math]p[/math] имела какой-нибудь суффикс, совпадающий с каким-нибудь префиксом, иначе говоря, чтобы [math]p[/math] имело автокорреляционный многочлен [math]C(z) \ne 1[/math]. В результате выходит, что при добавлении ко всем [math]\alpha \in S[/math] строки [math]p[/math] получим все строки из [math]T[/math], а также все строки, имеющие 2 перекрывающиеся вхождения строки [math]p[/math], иными словами, все строки вида [math]\gamma p_0p_1 \dots p_i \dots p_{k-1} p_{k-i} p_{k-i+1} \dots p_{k-1}[/math] (или, что то же, [math]\gamma p_0p_1 \dots p_{i-1} p_1 p_2 \dots p_{k-1}[/math]), где [math]\gamma[/math] — некоторый префикс [math]\alpha[/math], [math]i \in \overline{1, k-1}[/math], — номер некоторого ненулевого коэффициента автокорреляционного многочлена [math]C(z)[/math] строки [math]p[/math]. Нетрудно заметить, что [math]\gamma p_0p_1 \dots p_i \dots p_{k-1} p_{k-i} p_{k-i+1} \dots p_{k-1}[/math] можно представить как некую строку [math]t \in T[/math] с приписанным в конец суффиксом строки [math]p[/math] длины [math]i[/math]. В контексте комбинаторных объектов суффикс строки [math]p[/math] длины [math]i[/math] является комбинаторным объектом веса [math]i[/math], а его производящей функцией является [math]z^i[/math], то есть, по сути, это слагаемое автокорреляционного многочлена [math]C(z)[/math]. Тогда получаем следующее равенство: [math]S \times \{p\} = T + \dots + T \times \{p_{k-i} p_{k-i+1} \dots p_{k-1}\} + \dots = T \times C[/math], где [math]C[/math] — комбинаторный класс, соответствующий автокорреляционному многочлену [math]C(z)[/math].

В результате имеем 2 уравнения:

[math] \begin{cases} \{\epsilon\} + S \times \Sigma = S + T \\ S \times \{p\} = T \times C \\ \end{cases} [/math]

В терминах производящих функций эти уравнения выглядят так:

[math] \begin{cases} 1 + S(z) \cdot mz = S(z) + T(z) \\ S(z) \cdot z^k = T(z) \cdot C(z) \\ \end{cases} [/math]

Решим полученную систему относительно [math]S(z)[/math]:

[math] \begin{cases} T(z) = 1 + (mz-1)S(z) \\ S(z) \cdot z^k = (1 + (mz-1)S(z)) \cdot C(z) \\ \end{cases} [/math]

[math] S(z) \cdot (z^k - (mz-1)C(z)) = C(z) \\ [/math]

В итоге получаем искомую производящую функцию множества [math]S[/math] слов, не содержащих данную непустую [math]p[/math] как подстроку:

[math] S(z) = \dfrac{C(z)}{z^k - (mz-1)C(z)} \\ [/math], где [math]C(z)[/math] — автокорреляционный многочлен [math]p[/math], [math]m = |\Sigma|[/math], [math]k = |p|[/math].

Задача:

Пусть [math]\Sigma[/math] — данный алфавит, [math]p[/math] — данная непустая строка над алфавитом [math]\Sigma[/math]. Найти производящую функцию множества слов, содержащих [math]p[/math] как подстроку.

Пусть [math]m[/math] — мощность данного алфавита [math]\Sigma[/math]. Ясно, что слов длины [math]n[/math] над алфавитом мощности [math]m[/math] будет [math]m^n[/math] штук. Тогда производящей функцией множества всех слов над алфавитом мощности [math]m[/math] будет [math]\dfrac{1}{1-mz}[/math]. Вычтя из нее полученную ранее производящую функцию множества слов, не содержащих [math]p[/math] как подстроку, получим искомую производящую функцию: [math]\dfrac{1}{1-mz} - \dfrac{C(z)}{z^k - (mz-1)C(z)} = \dfrac{z^k - (mz-1)C(z) - (1-mz)C(z)}{(1-mz)(z^k - (mz-1)C(z))} = \dfrac{z^k}{(1-mz)(z^k + (1-mz)C(z))}[/math], где [math]C(z)[/math] — автокорреляционный многочлен [math]p[/math], [math]k = |p|[/math].

Задача:

Пусть [math]\Sigma[/math] — данный алфавит, [math]p[/math] — данная непустая строка над алфавитом [math]\Sigma[/math]. Найти производящую функцию множества слов, имеющих единственное вхождение [math]p[/math] как подстроки в самом конце.

Пусть [math]T[/math] — множество слов, содержащих [math]p[/math] как подстроку только в самом конце. Вернемся к системе уравнений, полученной при решении первой задачи, и воспользуемся найденным выражением [math]S(z)[/math]:

[math] \begin{cases} T(z) = 1 + (mz-1)S(z) \\ S(z) = \dfrac{C(z)}{z^k - (mz-1)C(z)} \\ \end{cases} [/math]

[math] T(z) = 1 + (mz-1)\dfrac{C(z)}{z^k - (mz-1)C(z)} \\ [/math]

В результате получаем искомую производящую функцию [math]T(z)[/math]:

[math] T(z) = \dfrac{z^k}{z^k - (mz-1)C(z)} \\ [/math], где [math]C(z)[/math] — автокорреляционный многочлен [math]p[/math], [math]m = |\Sigma|[/math], [math]k = |p|[/math].

См. также

• Производящая функция
• Метод производящих функций

Источники информации

• Васильев А. Т. Лекции по дискретной математике // Связь ПФ с регулярными языками, автокорреляция и пентагональная теорема Эйлера, 2020. URL: https://youtu.be/EmhScUQwXT0?t=2034.
• Wikipedia — Autocorrelation (words)