Изменения

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

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

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

'''Prefix_functionint''' [] prefixFunction(<tex>'''string''' s</tex>): <tex>\pi</tex> p[0] = 0 '''for''' i = 2 1 '''to''' ns.length - 1 k = <tex>\pi</tex>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>\pimathrm{while}</tex> в итоге выполнится не более <tex>n</tex> раз, что дает итоговую оценку времени алгоритма <tex>O(kn)</tex>. == Построение префикс-функции по Z-функции===== Постановка задачи ===Дан массив с корректной [[Z-функция | Z-функцией]] для строки <tex>s</tex>, получить за <tex>O(n) < k/tex> массив с префикс-функцией для строки <tex>s</tex>. Однако  === Описание алгоритма ===Пусть Z-функция хранится в силу массиве <tex>z[0 \pi(k) ldots n-1]</tex>. Префикс-функцию будем записывать в массив <tex>p[0 \ge 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>kj' </tex> изменяется не более чем на 1 внутри тела цикла c позиции <tex>fori' </tex>. Поскольку перед входом в цикл выполняется , причём <tex> k 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>forp</tex> от позиции <tex>i + z[i] - 1 </tex> до <tex>i</tex>значение <tex> j + 1, справедливость неравенства </tex>k где <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>\pimathrm{break}</tex> переводит внешний цикл на следующую итерацию, откуда получаем итоговую асимптотику <tex>O(in) < /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(n)</tex>, считая алфавит неограниченным. Каждое выполнение тела цикла  ===Описание алгоритма===Пусть в массиве <tex>whilep</tex> можно оплатить соответствующим уменьшение потенциальной хранятся значения префикс-функции, поскольку в <tex>\pi(k) s</tex> будет записан ответ. Пойдем по массиву <tex>p</tex> слева направо. Пусть мы хотим узнать значение < k 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 = 0 '''to''' p.length - 1 '''if''' p[i] == 0 s += new character '''else''' s += s[p[i] - 1] '''return''' s ===Доказательство корректности алгоритма===Докажем, что если нам дали корректную префикс-функцию, то наш алгоритм построит строку с такой же префикс-функцией. Также заметим, что строк с такой префикс-функцией может быть много, и алгоритм строит только одну изних. Пусть <tex>p</tex> {{---}} данная префикс-за этого амортизированная стоимость тела цикла функция, строку <tex>s</tex> построил наш алгоритм, <tex>forq </tex> {{---}} массив значений префикс-функции для <tex>s</tex>O(. Докажем корректность индукцией по длине массива префикс-функции полученной строки. Для начала заметим, что на предыдущие значения массива <tex> q </tex> прибавление нового символа не влияет, так как при подсчёте префикс-функции на <tex> i </tex>-ой позиции рассматриваются символы на позициях не больше <tex> i </tex>. Поэтому достаточно показать, что очередное значение префикс-функции будет вычислено правильно.* База очевидна для строки длины <tex>1</tex>.* Переход: пусть до <tex>n</tex>-ой позиции мы построили строку, что <tex>p[0 \ldots n - 1] = q[0 \ldots n - 1]</tex>. Возможны два случая:** <tex>p[n] = 0</tex>. Тогда мы добавляем новый символ, поэтому <tex>q[n]</tex> тоже будет равно <tex>0</tex>. ** <tex>p[n] > 0</tex>. Бордер строки <tex> s[0 \ldots n - 1] </tex> имеет длину <tex> p[n-1] = q[n-1)] </tex>. Так Поэтому если дописать к строке <tex> s </tex> символ <tex> s[q[n] - 1] </tex>, то бордер нашей новой строки <tex> s[0 \ldots n] </tex> станет равен <tex> p[n] </tex>, как количество итераций можно увидеть на [[Префикс-функция#Эффективный алгоритм | рисунке]]. == Критерий корректности значений префикс-функции =={{Задача|definition = Дан массив значений префикс-функции некоторой строки <tex>s</tex>, необходимо проверить, корректен ли он за <tex>O(n|s|)</tex>. Так же узнать размер минимального алфавита, при котором он корректен.}} === Решение ===Если выполняется неравенство <tex>0 \leqslant p[i + 1] \leqslant p[i] + 1</tex>, то мы можем построить строку из алгоритма выше, и поскольку конечное значит префикс-функция корректна. Найдем минимальный алфавит, при котором префикс-функция корректна. Если значение потенциальной префикс-функции по величине в текущей ячейке больше нуля, буква известна и алфавит не меньшенуждается в добавлении новой буквы. Иначе, необходимо исключить все ранее известные буквы, возвращаясь и проверяя для меньших префиксов. Если все уже известные буквы использованы, понятно что, необходимо добавить новую букву. === Доказательство корректности ===Докажем, что найденнный выше алфавит минимален от противного. Допустим, существует строка, использующая алфавит меньшей мощности. Рассмотрим первое вхождение буквы, чем ее начальное значениекоторая есть в нашем алфавите, полное время работы а в наихудшем случае равно их отсутствует. Понятно, что для этого символа префикс-функция равна 0, т.к. мы добавили новую букву. Пройдемся циклом <tex>\mathrm{while}</tex>Oпо подпрефиксам. Т.к. в меньшем решении буква не новая, то она увеличит подпрефикс и префикс-функция в новой строке будет отличаться от нуля в этом символе, а должна равняться нулю. Противоречие, следовательно не существует алфаивта меньшей мощности, чем найденный алгоритмом выше. === Псевдокод === '''bool''' is_correct(n'''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, false) 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[i] = j; '''break''' '''if''' s[i] == -1 s[i] = c++ '''else''' s[i] = s[p[i] - 1] '''return''' c == См. также ==*[[Z-функция|Z-функция]]*[[Алгоритм Кнута-Морриса-Пратта|Алгоритм Кнута-Морриса-Пратта]]== Источники информации ==*[[wikipedia:ru:Префикс-функция | Википедия {{---}} Префикс-функция]]*[http:/tex>/e-maxx.ru/algo/prefix_function MAXimal :: algo :: Префикс-функция]* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С.1296 ISBN 978-5-8459-0857-5 

== Литература ==[[Категория: Алгоритмы и структуры данных]]Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы[[Категория: построение и анализ. {{---}} 2-е изд. {{---}} М.Поиск подстроки в строке]][[Категория: Издательский дом «Вильямс», 2007. {{---}} С. 1296.Точный поиск]]