Изменения

Здесь и далее считаем, что символы в строках нумеруются с <tex>10</tex>.

Определим префикс-функцию от строки <tex>s</tex> в позиции <tex>i</tex> следующим образом: <tex>\pi(s, i) = \max\limits_{k = 1..\ldots i - 1} \{k : </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(<tex>\pi</tex>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>\pip[i + 1] \leqslant \pip[i] + 1</tex>. Чтобы показать это, рассмотрим суффикс,оканчивающийся на позиции <tex>i + 1</tex> и имеющий длину <tex>\pip[i + 1]</tex>, удалив из него последний символ, мы получим суффикс, оканчивающийся на позиции <tex>i</tex> и имеющий длину <tex>\pip[i + 1] - 1</tex>, следовательно неравенство <tex>\pip[i + 1] > \pip[i] + 1</tex> неверно.*Избавимся от явных сравнений строк. Пусть мы вычислили <tex>\pip[i]</tex>, тогда, если <tex>s[i + 1] = s[\pip[i]]</tex>, то <tex>\pip[i + 1] = \pip[i] + 1</tex>. Если окажется, что <tex>s[i + 1] \ne s[\pip[i]]</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>.

'''int'''[] prefixFunction('''string''' s): <tex>\pi</tex> p[10] = 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> z</tex>[[Z-функция | Z-функцией ]] для строки <tex>s</tex>, получить за <tex>O(n)</tex> массив с префикс-функцией для строки <tex>s</tex>.

Пусть <tex>Z</tex>-функция хранится в массиве <tex>z[0 \ldots n-1..n],</tex> префикс. Префикс-функцию будем записывать в массив <tex>p[0 \ldots n-1..n]</tex>.Пойдем по массиву <tex>z</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>ki </tex>, где а потом пытаемся установить значение <tex> j' </tex> c позиции <tex> i' </tex>, причём <tex> i < i' </tex>k и < tex> i + j = i' + j' </tex>, то такое изменение с позиции <tex> i' </tex> только уменьшит значение <tex> p[i + j]</tex>, действительно. Действительно, значение после первого присвоения <tex>p_{old}p[i + j] = i + j - k + 1 > i + j - i + 1 ' = p_{new}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>.  Рассмотрим корректность алгоритма. Предположим, что наш алгоритм неправильно посчитал какие-то значение <tex>p[i]</tex>. Пусть <tex>ans[1..n]</tex> это массив, содержащий корректную префикс-функцию. Рассмотрим позицию в которой наш алгоритм посчитал некорректно, пусть это позиция <tex>i</tex>. Заметим, что <tex>ans[i]\geqslant p[i]</tex> так как алгоритм записывает длину подстроки, оканчивающуюся на <tex>i</tex>-ом символе, соответственно правильный ответ, не может быть меньше нашего. Предположим, что <tex>ans[i] > p[i]</tex>, посмотрим на значение <tex>z[i - ans[i] + 1]</tex> оно больше либо равно <tex>ans[i]</tex>. Но тогда наш алгоритм бы записал в <tex>p[i]</tex> корректное значение.

'''int'''[] buildPrefixFunctionFromZFunction('''int'''[] z): '''int'''[] p = '''new int'''[z.length] fill(p, 0) '''for''' i = 2 1 '''to''' z.length - 1

Пусть мы хотим узнать значение <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>.

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> p[n - 1] s</tex>, а из свойств следуетнеобходимо проверить, что корректен ли он за <tex> p[n - 1] \geqslant p[n] - 1 O(|s|)</tex>. По предположению индукцию значение Так же узнать размер минимального алфавита, при котором он корректен.}} === Решение ===Если выполняется неравенство <tex> q0 \leqslant p[n - i + 1] </tex> будет вычислено верно. А если значение префикс-функции не увеличивается, значит, символ <tex> s\leqslant p[ni] + 1</tex> должен продолжить префикс меньшей длины, а в текущее значение префикс-функции запишется как раз длина нового [[Период_и_бордерто мы можем построить строку из алгоритма выше,_их_связь#Определения|бордера]]. Для этого будут использованы значения значит префикс-функции с меньшими индексами, которые посчитаны верно, опять же по предположению индукциифункция корректна.