Изменения

{{Определение|definition = '''Префикс-функция ''' ''(англ. prefix-function)'' от строки <tex>s</tex> {{---}} функция <tex>\pi(i) = \max\limits_{k = 1..i - 1массив длин наибольших [[Период_и_бордер,_их_связь#Определения|бордеров]] для каждой позиции этой строки}} \{ 0Здесь и далее считаем, k : что символы в строках нумеруются с </tex> <tex>s[1..k] = s[i - k + 1..i] \}0</tex>.

Здесь и далее считаемОпределим префикс-функцию от строки <tex>s</tex> в позиции <tex>i</tex> следующим образом: <tex>\pi(s, что символы в строках нумеруются с i) = \max\limits_{k = 1 \ldots i} \{k : </tex> <tex>s[0 \ldots k - 1] = s[i - k + 1 \ldots i] \}</tex>. Если мы не нашли такого <tex>k</tex>, то <tex>\pi(s, i)=0</tex>. ==АлгоритмНаивный алгоритм==Наивный алгоритм вычисляет префикс -функцию непосредственно по определению, сравнивая префиксы и суффиксы строк. Обозначим длину строки за <tex>n</tex>. Будем считать, что префикс-функция хранится в массиве <tex> p </tex>.

'''Prefix_functionint''' [] prefixFunction(<tex>'''string''' s</tex>): <tex>\pi</tex> '''int'''[] p = '''int'''[0,.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] <tex>\pi</tex>p[i] = k '''return''' <tex>\pi</tex>p

Рассмотрим строку <tex>abcabcd</tex>, для которой значение префикс-функции равно <tex>[0,0,0,1,2,3,0]</tex>.

==ОптимизацияЭффективный алгоритм==

*Следует заметитьЗаметим, что <tex>\pi(p[i) + 1] \le \pi(leqslant p[i-1) ] + 1</tex>. По определению префикс функции верноЧтобы показать это, рассмотрим суффикс, что оканчивающийся на позиции <tex>i + 1</tex> и имеющий длину <tex>sp[i + 1..\pi(]</tex>, удалив из него последний символ, мы получим суффикс, оканчивающийся на позиции <tex>i</tex> и имеющий длину <tex>p[i)+ 1] = s- 1</tex>, следовательно неравенство <tex>p[i - \pi(+ 1] > p[i) ] + 1</tex> неверно.* Избавимся от явных сравнений строк.Пусть мы вычислили <tex>p[i]</tex>. В частности, получаетсятогда, что если <tex>s[1..\pi(i) - + 1] = s[p[i - \pi(i) + 1..i - 1]]</tex>. Поскольку , то <tex>\pip[i + 1] = p[i] + 1</tex> это наибольший префикс равный суффиксу. Если окажется, то что <tex>\pi(s[i - + 1) ] \ge \pi(ne s[p[i) - 1]]</tex>, то нужно попытаться попробовать подстроку меньшей длины. *Избавимся от явных сравнений строк. Для Хотелось бы сразу перейти к такому [[Период_и_бордер,_их_связь#Определения|бордеру]] наибольшей длины, для этого подберем такое <tex>k</tex>, что <tex>k = \pi(p[i) ] - 1</tex>. Делаем это следующим образом. За исходное <tex>k</tex> необходимо взять <tex>\pi(p[i - 1)]</tex>, что следует из первого пункта. В случае, когда символы <tex>s[k+1]</tex> и <tex>s[i]</tex> не совпадают, <tex>\pi(p[k)- 1]</tex> {{---}} следующее потенциальное наибольшее значение <tex>k</tex>, что видно из рисунка. Последнее утверждение верно, пока <tex>k>0</tex>, что позволит всегда найти его следующее значение. Если <tex>k=0</tex>, то <tex>\pi(p[i)]=1</tex> при <tex>s[i] = s[1]</tex> , иначе <tex>\pi(p[i)]=0</tex>. [[Файл:mprfx.jpg|800px]]

'''Prefix_functionint''' [] prefixFunction(<tex>'''string''' s</tex>): <tex>\pi</tex> p[10] = 0 k = 0 '''for''' i = 2 1 '''to''' ns.length - 1 k = p[i - 1] '''while''' k > 0 && '''and''' s[i] != s[k + 1] k = <tex>\pi</tex>p[k- 1] '''if''' s[i] == s[k + 1] k++ <tex>\pi</tex> p[i] = k '''return''' <tex>\pi</tex>p

Время работы алгоритма составит <tex>O(n)</tex>. Для доказательства этого нужно заметить, что итоговое количество итераций цикла <tex>\mathrm{while}</tex> определяет асимптотику алгоритма. Теперь стоит отметить, что <tex>k</tex> увеличивается на каждом шаге не более чем на единицу, значит максимально возможное значение <tex>k = n - 1</tex>. Поскольку внутри цикла <tex>\mathrm{while}</tex> значение <tex>k</tex> лишь уменьшается, получается, что <tex>k</tex> не может суммарно уменьшиться больше, чем <tex>n-1</tex> раз. Значит цикл <tex>\mathrm{while}</tex> в итоге выполнится не более <tex>n</tex> раз, что дает итоговую оценку времени алгоритма <tex>O(n)</tex>. == Построение префикс-функции по Z-функции===== Постановка задачи ===Дан массив с корректной [[Z-функция | Z-функцией]] для строки <tex>s</tex>, получить за <tex>O(n)</tex> массив с префикс-функцией для строки <tex>s</tex>. === Описание алгоритма ===Пусть Z-функция хранится в массиве <tex>z[0 \ldots n-1]</tex>. Префикс-функцию будем записывать в массив <tex>p[0 \ldots 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> (как изображено на рисунке).  Также заметим, что если мы уже установили в какую-то позицию значение <tex> j </tex> с позиции <tex> i </tex>, а потом пытаемся установить значение <tex> j' </tex> c позиции <tex> i' </tex>, причём <tex> i < i' </tex> и <tex> i + j = i' + j' </tex>, то изменение с позиции <tex> i' </tex> только уменьшит значение <tex> p[i + j]</tex>. Действительно, значение после первого присвоения <tex>p[i + j] = j > j' = p[i' + j']</tex>. В итоге получаем алгоритм: идем слева направо по массиву <tex>z</tex> и, находясь на позиции <tex>i</tex>, пытаемся записать в <tex>p</tex> от позиции <tex>i + z[i] - 1 </tex> до <tex>i</tex> значение <tex> j + 1,</tex> где <tex>j</tex> пробегает все значения <tex> 0 \dots z[i] - 1</tex>, пока не наткнемся на уже инициализированный элемент. Слева от него все значения тоже нет смысла обновлять, поэтому прерываем эту итерацию.  Убедимся, что алгоритм работает за линейное время (см. псевдокод). Каждый элемент устанавливается ровно один раз. Дальше на нем может случиться только <tex>\mathrm{break}</tex>. Поэтому в итоге внутренний цикл суммарно отработает за количество установленных значений и количество <tex>\mathrm{break}</tex>. Количество установленных значений {{---}} <tex> n</tex>. А число <tex>\mathrm{break}</tex> тоже будет не больше <tex>n</tex>, так как каждый <tex>\mathrm{break}</tex> переводит внешний цикл на следующую итерацию, откуда получаем итоговую асимптотику <tex>O(n)</tex>.  [[Файл:ZP4.jpg|800px]] === Псевдокод === '''int'''[] buildPrefixFunctionFromZFunction('''int'''[] z): '''int'''[] p = '''int'''[z.length] fill(p, 0) '''for''' i = 1 '''to''' z.length - 1 '''for''' j = z[i] - 1 '''downto''' 0 '''if''' p[i + j] > 0 '''break''' '''else''' p[i + j] = j + 1 '''return''' p

Восстановить строку по префикс-функции за <tex>O(Nn)</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>.

'''for''' i = 0 '''to''' p.length - 1: '''if''' p[i] == 0:

'''else:''' s += s[p[i]- 1]

Пусть <tex>p</tex> {{---}} данная префикс-функция, <tex>s'</tex> правильная строка, строку <tex>s</tex> построил наш алгоритм, <tex> q </tex> {{---}} массив значений префикс-функции для <tex>s</tex>.

* Переход: пусть до <tex>n</tex>-ой позиции мы построили строку, что <tex>p[1..0 \ldots n - 1] = q[1..0 \ldots n - 1]</tex>. Возможны два случая:

** <tex>p[n] > 0</tex>. По свойствам префикс-функции Бордер строки <tex> s'[0 \ldots n - 1] </tex> имеет длину <tex> p[n]-1] = s'q[n-1] </tex> {{---}} суффикс и префикс строки . Поэтому если дописать к строке <tex> s' </tex> длины символ <tex> ps[q[n] - 1] </tex> продолжаются одним символом, значит, надо на текущую позицию то бордер нашей новой строки <tex> s [0 \ldots n] </tex> поставить символ станет равен <tex> s[p[n]] </tex>, как можно увидеть на [[Префикс-функция#Эффективный алгоритм | рисунке]]. Если значение  == Критерий корректности значений префикс-функции =={{Задача|definition = Дан массив значений префикс-функции увеличиваетсянекоторой строки <tex>s</tex>, значитнеобходимо проверить, текущим символом продолжается префикс длины корректен ли он за <tex> p[n - 1] O(|s|)</tex>. Так же узнать размер минимального алфавита, а из свойств следует, что при котором он корректен.}} === Решение ===Если выполняется неравенство <tex> 0 \leqslant p[n - i + 1] \geqslant leqslant p[ni] - + 1 </tex>, то мы можем построить строку из алгоритма выше, значит префикс-функция корректна. По предположению индукцию  Найдем минимальный алфавит, при котором префикс-функция корректна. Если значение префикс-функции в текущей ячейке больше нуля, буква известна и алфавит не нуждается в добавлении новой буквы. Иначе, необходимо исключить все ранее известные буквы, возвращаясь и проверяя для меньших префиксов. Если все уже известные буквы использованы, понятно что, необходимо добавить новую букву. === Доказательство корректности ===Докажем, что найденнный выше алфавит минимален от противного. Допустим, существует строка, использующая алфавит меньшей мощности. Рассмотрим первое вхождение буквы, которая есть в нашем алфавите, а в их отсутствует. Понятно, что для этого символа префикс-функция равна 0, т.к. мы добавили новую букву. Пройдемся циклом <tex> q[n - 1] \mathrm{while}</tex> будет вычислено вернопо подпрефиксам. Т.к. А если значение в меньшем решении буква не новая, то она увеличит подпрефикс и префикс-функции функция в новой строке будет отличаться от нуля в этом символе, а должна равняться нулю. Противоречие, следовательно не увеличиваетсясуществует алфаивта меньшей мощности, значитчем найденный алгоритмом выше. === Псевдокод === '''bool''' is_correct('''int'''[] p): '''for''' i = 0 '''to''' p.length - 1 '''if''' i > 0 && p[i] > p[i - 1] + 1 || p[i] < 0 '''return''' '''false''' '''return''' '''true'''  '''int''' minimal_alphabet('''int'''[] p): c = 1 s[0] = 0 '''for''' i = 1 '''to''' p.length - 1 '''if''' p[i] == 0 '''fill'''(used, символ <texfalse) k = p[i - 1] '''while''' k > 0 used[s[k]] = '''true''' k = p[k - 1] s[i] = -1 '''for''' j = 1 '''to''' c '''if''' !used[j] s[ni] = j; '''break''' '''if''' s[i] == -1 s[i] = c++ '''else''' s[i] = s[p[i] - 1] '''return''' c == См. также ==*[[Z-функция|Z-функция]]*[[Алгоритм Кнута-Морриса-Пратта|Алгоритм Кнута-Морриса-Пратта]]== Источники информации ==*[[wikipedia:ru:Префикс-функция | Википедия {{---}} Префикс-функция]] <*[http://e-maxx.ru/algo/tex> должен продолжить префикс меньшей длиныprefix_function MAXimal :: algo :: Префикс-функция]* Кормен Т., Лейзерсон Ч., а в текущее значение префиксРивест Р. Алгоритмы: построение и анализ. {{---}} 2-функции запишется как раз длина нового бордерае изд. Для этого будут использованы значения префикс{{---функции с меньшими индексами}} М.: Издательский дом «Вильямс», которые посчитаны верно, опять же по препдположению индукции2007. {{---}} С.1296 ISBN 978-5-8459-0857-5

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