Изменения
→Эффективный алгоритм
{{Определение
|definition = '''Префикс-функция''' ''(англ. prefix-function)'' от строки {{---}} массив длин наибольших [[Период_и_бордер,_их_связь#Определения|бордеров]] для каждой позиции этой строки}}
Здесь и далее считаем, что символы в строках нумеруются с <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>.
==Наивный алгоритм==
===Псевдокод===
'''int'''[] prefixFunction('''string''' s):
'''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
Вносятся несколько важных замечаний:
* Заметим, что <tex>p[i + 1] \leqslant p[i] + 1</tex>. Чтобы показать это, рассмотрим суффикс,оканчивающийся на позиции <tex>i + 1</tex> и имеющий длину <tex>p[i + 1]</tex>, удалив из него последний символ, мы получим суффикс, оканчивающийся на позиции <tex>i</tex> и имеющий длину <tex>p[i + 1] - 1</tex>, следовательно неравенство <tex>p[i + 1] > p[i] + 1</tex> неверно.
* Избавимся от явных сравнений строк. Пусть мы вычислили <tex>p[i]</tex>, тогда, если <tex>s[i + 1] = s[p[i]]</tex>, то <tex>p[i + 1] = p[i] + 1</tex>. Если окажется, что <tex>s[i + 1] \ne s[p[i]]</tex>, то нужно попытаться попробовать подстроку меньшей длины. Хотелось бы сразу перейти к такому [[Период_и_бордер,_их_связь#Определения|бордеру]] наибольшей длины, для этого подберем такое <tex>k</tex>, что <tex>k = p[i] - 1</tex>. Делаем это следующим образом. За исходное <tex>k</tex> необходимо взять <tex>p[i - 1]</tex>, что следует из первого пункта. В случае, когда символы <tex>s[k+1]</tex> и <tex>s[i]</tex> не совпадают, <tex>p[k- 1]</tex> {{---}} следующее потенциальное наибольшее значение <tex>k</tex>, что видно из рисунка. Последнее утверждение верно, пока <tex>k>0</tex>, что позволит всегда найти его следующее значение. Если <tex>k=0</tex>, то <tex>p[i]=1</tex> при <tex>s[i] = s[1]</tex> , иначе <tex>p[i]=0</tex>.
[[Файл:mprfx.jpg|800px]]
===Псевдокод===
'''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] k = p[k- 1] '''if''' s[i] == s[k + 1]
k++
p[i] = k
== Построение префикс-функции по Z-функции==
=== Постановка задачи ===
Дан массив с корректной [[Z-функция | Z-функцией ]] для строки <tex>s</tex>, получить за <tex>O(n)</tex> массив с префикс-функцией для строки <tex>s</tex>.
=== Описание алгоритма ===
Пусть Z-функция хранится в массиве <tex>z[0 \ldots n-1..n]</tex>. Префикс-функцию будем записывать в массив <tex>p[0 \ldots n-1..n]</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'''[] buildPrefixFunctionFromZFunction('''int'''[] z): '''int'''[] p = '''new 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>.
=== Реализация ===
s += new character
'''else'''
s += s[p[i]- 1]
'''return''' s
Докажем, что если нам дали корректную префикс-функцию, то наш алгоритм построит строку с такой же префикс-функцией. Также заметим, что строк с такой префикс-функцией может быть много, и алгоритм строит только одну из них.
Пусть <tex>p</tex> {{---}} данная префикс-функция, <tex>s'</tex> правильная строка, строку <tex>s</tex> построил наш алгоритм, <tex> q </tex> {{---}} массив значений префикс-функции для <tex>s</tex>.
Докажем корректность индукцией по длине массива префикс-функции полученной строки. Для начала заметим, что на предыдущие значения массива <tex> q </tex> прибавление нового символа не влияет, так как при подсчёте префикс-функции на <tex> i </tex>-ой позиции рассматриваются символы на позициях не больше <tex> i </tex>. Поэтому достаточно показать, что очередное значение префикс-функции будет вычислено правильно.
* База очевидна для строки длины <tex>1</tex>.
* Переход: пусть до <tex>n</tex>-ой позиции мы построили строку, что <tex>p[1..0 \ldots n - 1] = q[1..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] = 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> должен продолжить префикс меньшей длины, а в текущее значение префикс-функции запишется как раз длина нового [[Период_и_бордерто мы можем построить строку из алгоритма выше,_их_связь#Определения|бордера]]. Для этого будут использованы значения значит префикс-функции с меньшими индексами, которые посчитаны верно, опять же по предположению индукциифункция корректна.
Найдем минимальный алфавит, при котором префикс-функция корректна. Если значение префикс-функции в текущей ячейке больше нуля, буква известна и алфавит не нуждается в добавлении новой буквы. Иначе, необходимо исключить все ранее известные буквы, возвращаясь и проверяя для меньших префиксов. Если все уже известные буквы использованы, понятно что, необходимо добавить новую букву.
=== Доказательство корректности ===
Докажем, что найденнный выше алфавит минимален от противного. Допустим, существует строка, использующая алфавит меньшей мощности. Рассмотрим первое вхождение буквы, которая есть в нашем алфавите, а в их отсутствует. Понятно, что для этого символа префикс-функция равна 0, т.к. мы добавили новую букву. Пройдемся циклом <tex>\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, 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
== См. также ==
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Поиск подстроки в строке]]
[[Категория:Точный поиск]]
