Изменения
Нет описания правки
{{Определение
|definition = '''Префикс-функция''' ''(англ. prefix-function)'' от строки {{---}} массив длин наибольших [[Период_и_бордер,_их_связь#Определения|бордеров]] для каждой позиции этой строки}}
Здесь и далее считаем, что символы в строках нумеруются с <tex>10</tex>.
Определим префикс-функцию от строки <tex>s</tex> в позиции <tex>i</tex> следующим образом: <tex>\pi(s, i) = \max\limits_{k = 10..i - 1} \{k : </tex> <tex>s[10..k] = s[i - k + 1..i] \}</tex>. Если мы не нашли такого <tex>k</tex>, то <tex>\pi(s, i)=0</tex>.
==Наивный алгоритм==
'''int'''[] p = '''int'''[s.length]
fill(p, 0)
'''for''' i = 1 0 '''to''' ns.length - 1 '''for''' k = 1 0 '''to''' i- 1 '''if''' s[10..k] == s[i - k + 1..i]
p[i] = k
'''return''' p
===Псевдокод===
'''int'''[] prefixFunction('''string''' s):
p[10] = 0 '''for''' i = 2 1 '''to''' ns.length - 1
k = p[i - 1]
'''while''' k > 0 '''and''' s[i] != s[k + 1]
=== Описание алгоритма ===
Пусть Z-функция хранится в массиве <tex>z[10..n-1]</tex>. Префикс-функцию будем записывать в массив <tex>p[10..n-1]</tex>.
Заметим, что если <tex>z[i] > 0, </tex> то для всех элементов с индексом <tex>i + j</tex>, где <tex>0 \leqslant j < z[i] </tex>, значение <tex>p[i + j] </tex> будет не меньше, чем длина подстроки с <tex> i </tex> по <tex> i + j</tex>, что равно <tex>j + 1</tex> (как изображено на рисунке).
'''int'''[] p = '''int'''[z.length]
fill(p, 0)
'''for''' i = 2 1 '''to''' z.length - 1
'''for''' j = z[i] - 1 '''downto''' 0
'''if''' p[i + j] > 0
Пусть в массиве <tex>p</tex> хранятся значения префикс-функции, в <tex>s</tex> будет записан ответ. Пойдем по массиву <tex>p</tex> слева направо.
Пусть мы хотим узнать значение <tex>s[i]</tex>. Для этого посмотрим на значение <tex>p[i]</tex>: если <tex>p[i] =0</tex>, тогда в <tex>s[i]</tex> запишем новый символ, иначе <tex>s[i] = s[p[i]- 1]</tex>. Обратим внимание, что <tex>s[p[i]- 1]</tex> нам уже известно, так как <tex>p[i] - 1 < i</tex>.
=== Реализация ===
'''string''' buildFromPrefix('''int'''[] p):
s = ""
'''for''' i = 1 0 '''to''' p.length- 1
'''if''' p[i] == 0
s += new character
'''else'''
s += s[p[i]- 1]
'''return''' s
Докажем корректность индукцией по длине массива префикс-функции полученной строки. Для начала заметим, что на предыдущие значения массива <tex> q </tex> прибавление нового символа не влияет, так как при подсчёте префикс-функции на <tex> i </tex>-ой позиции рассматриваются символы на позициях не больше <tex> i </tex>. Поэтому достаточно показать, что очередное значение префикс-функции будет вычислено правильно.
* База очевидна для строки длины <tex>1</tex>.
* Переход: пусть до <tex>n</tex>-ой позиции мы построили строку, что <tex>p[10..n - 1] = q[10..n - 1]</tex>. Возможны два случая:
** <tex>p[n] = 0</tex>. Тогда мы добавляем новый символ, поэтому <tex>q[n]</tex> тоже будет равно <tex>0</tex>.
** <tex>p[n] > 0</tex>. Бордер строки <tex> s[10..n - 1] </tex> имеет длину <tex> p[n-1] = q[n-1] </tex>. Поэтому если дописать к строке <tex> s </tex> символ <tex> s[q[n]- 1] </tex>, то бордер нашей новой строки <tex> s[10..n] </tex> станет равен <tex> p[n] </tex>, как можно увидеть на [[Префикс-функция#Эффективный алгоритм | рисунке]].
== См. также ==
