668
правок
Изменения
Нет описания правки
===Время работы===
Время работы алгоритма составит <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-функции]]==
=== Постановка задачи ===
Дан массив с корректной <tex> z-</tex> функцией для строки <tex>s</tex>, получить за <tex>O(N)</tex> массив с префикс-функцией для строки <tex>s</tex>
=== Описание алгоритма ===
Пусть <tex>Z-</tex> функция хранится в массиве <tex>z[1..n],</tex> префикс-функцию будем записывать в массив <tex>p[1..n]</tex>.
Пойдем по массиву <tex>z</tex> слева направо, заметим, что если <tex>z[i] > 0, </tex> то для всех элементов с индексом <tex>i + j</tex>, где <tex>0 < j < z[i] </tex> значение <tex>p[i + j] </tex> будет не меньше, чем <tex>j + 1, </tex> в силу определения префикс и <tex>Z</tex> функции. Также заметим, что если мы уже установили значение в какое-то <tex>p[k]</tex> то менять уже не нужно, так как это только уменьшит значение <tex>p[k].</tex> В итоге получаем алгоритм, идем слева направо по массиву <tex>z</tex>. Пусть мы сейчас находимся на позиции <tex>i</tex> тогда пытаемся записать в <tex>p</tex> от позиции <tex>i + z[i] - 1 </tex> до <tex>i</tex> значение <tex> j - i + 1,</tex> где <tex>j</tex> пробегает все значения <tex> 0.. z[i] - 1.</tex> В итоге каждый элемент в <tex>p</tex> будет просмотрен не более двух раз, откуда получаем асимптотику <tex>O(N).</tex>
=== Псевдокод ===
'''int'''[] buildPrefixFunctionFromZFunction('''int'''[] z)
'''int'''[] p = '''new int'''[z.length]
'''for''' i = 0 '''to''' p.length - 1
'''if''' z[i] > 0
'''for''' j = z[i] - 1 '''downto''' 0
'''if''' p[i + j] > 0 '''break'''
'''else''' p[i + j] = j + 1
'''return''' p
=== Доказательство корректности ===
Пусть наш алгоритм неправильно посчитал какие-то значение <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> корректное значение.
==Построение строки по префикс-функции==
** <tex>p[n] > 0</tex>. По свойствам префикс-функции <tex> s'[p[n]] = s'[n] </tex> {{---}} суффикс и префикс строки <tex> s' </tex> длины <tex> p[n] </tex> продолжаются одним символом, значит, надо на текущую позицию строки <tex> s </tex> поставить символ <tex> s[p[n]] </tex>. Если значение префикс-функции увеличивается, значит, текущим символом продолжается префикс длины <tex> p[n - 1] </tex>, а из свойств следует, что <tex> p[n - 1] \geqslant p[n] - 1 </tex>. По предположению индукцию значение <tex> q[n - 1] </tex> будет вычислено верно. А если значение префикс-функции не увеличивается, значит, символ <tex> s[n] </tex> должен продолжить префикс меньшей длины, а в текущее значение префикс-функции запишется как раз длина нового [[Период_и_бордер,_их_связь#Определения|бордера]]. Для этого будут использованы значения префикс-функции с меньшими индексами, которые посчитаны верно, опять же по предположению индукции.
== См. также ==
