Изменения

Здесь и далее считаем, что символы в строках нумеруются с <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>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'[p[0 \ldots n- 1]] = s'[n] </tex> {{---}} суффикс и префикс строки <tex> s' </tex> длины имеет длину <tex> p[n-1] = q[n-1] </tex> продолжаются одним символом, значит, надо на текущую позицию строки . Поэтому если дописать к строке <tex> s </tex> поставить символ <tex> s[pq[n]] </tex>. Если значение префикс-функции увеличивается, значит, текущим символом продолжается префикс длины <tex> p[n - 1] </tex>, а из свойств следует, что то бордер нашей новой строки <tex> ps[n - 1] 0 \geqslant p[ldots n] - 1 </tex>. По предположению индукцию значение станет равен <tex> qp[n - 1] </tex> будет вычислено верно. А если значение префикс-функции не увеличивается, значит, символ <tex> s[n] </tex> должен продолжить префикс меньшей длины, а в текущее значение префикс-функции запишется как раз длина нового можно увидеть на [[Период_и_бордер,_их_связьПрефикс-функция#ОпределенияЭффективный алгоритм |бордерарисунке]]. Для этого будут использованы значения префикс-функции с меньшими индексами, которые посчитаны верно, опять же по предположению индукции.

== Построение Критерий корректности значений префикс-функции по <tex>Z-</tex> функции =={{Задача|definition === Постановка задачи ===Дан массив с корректной значений префикс-функции некоторой строки <tex> z-s</tex> функцией для строки , необходимо проверить, корректен ли он за <tex>O(|s|)</tex>. Так же узнать размер минимального алфавита, получить за при котором он корректен.}} === Решение ===Если выполняется неравенство <tex>O(N)0 \leqslant p[i + 1] \leqslant p[i] + 1</tex> массив с , то мы можем построить строку из алгоритма выше, значит префикс-функция корректна. Найдем минимальный алфавит, при котором префикс-функция корректна. Если значение префикс-функцией функции в текущей ячейке больше нуля, буква известна и алфавит не нуждается в добавлении новой буквы. Иначе, необходимо исключить все ранее известные буквы, возвращаясь и проверяя для меньших префиксов. Если все уже известные буквы использованы, понятно что, необходимо добавить новую букву. === Доказательство корректности ===Докажем, что найденнный выше алфавит минимален от противного. Допустим, существует строка, использующая алфавит меньшей мощности. Рассмотрим первое вхождение буквы, которая есть в нашем алфавите, а в их отсутствует. Понятно, что для строки этого символа префикс-функция равна 0, т.к. мы добавили новую букву. Пройдемся циклом <tex>s\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 = Описание алгоритма ===Пусть <tex>Z-</tex> функция хранится в массиве <tex>z[1'''to''' p..n],</tex> префиксlength -функцию будем записывать в массив <tex>p[1..n]</tex>.Пойдем по массиву <tex>z</tex> слева направо, заметим, что если <tex>z '''if''' p[i] > == 0 '''fill'''(used, </tex> то для всех элементов с индексом <tex>i + j</tex>, где <tex>0 < j < zfalse) k = p[i- 1] </tex '''while''' k > значение <tex>p0 used[i + j] </tex> будет не меньше, чем <tex>j + 1, </tex> в силу определения префикс и <tex>Z</tex> функции. Также заметим, что если мы уже установили значение в какое-то <tex>ps[k]</tex> то менять уже не нужно, так как это только уменьшит значение <tex>] = '''true''' k = p[k- 1].</tex> В итоге получаем алгоритм, идем слева направо по массиву <tex>z</tex>. Пусть мы сейчас находимся на позиции <tex>i</tex> тогда пытаемся записать в <tex>p</tex> от позиции <tex>i + z s[i] = - 1 </tex> до <tex> '''for''' j = 1 '''to''' c '''if''' !used[j] s[i</tex> значение <tex> ] = j ; '''break''' '''if''' s[i] == - 1 s[i ] = c+ 1,</tex> где <tex>j</tex> пробегает все значения <tex> 0.. z+ '''else''' s[i] = s[p[i] - 1.</tex>] '''return''' c

*[http://e-maxx.ru/algo/prefix_function MAXimal :: algo {{---}} :: Префикс-функция]